Can someone code review my "Distance between nodes in a BT"?

In summary, the conversation discusses a coding test and the rejection of a solution used for the test. The code in question is a tree-traversal algorithm used to find the nearest common ancestor and distance between two nodes in the tree. The reviewer suggests adding more comments and making variable names more descriptive for better code readability.
  • #1
SlurrerOfSpeech
141
11
Here's the solution I used for an online coding test with a major employer and I got rejected. Let me know about improvements I could make. Thanks.

Code:
using System;
using System.Collections.Generic;
using System.Linq;

class Node
{
    public int Val { get; set; }
    public Node Right { get; set; }   
    public Node Left { get; set; }
    public Node(int val) { Val = val; }
}public class Solution
{ 
    static Node _root = null;
   
    static void AddToTree(int val)
    {
        if(_root == null)
            _root = new Node(val);   
       
        for(Node cur = _root; ; )
        {   
            if(cur.Val < val)
            {
                if(cur.Right == null)
                {
                    cur.Right = new Node(val);
                    break;
                }
                else
                {
                    cur = cur.Right;
                }
            }
            else if(val < cur.Val)
            {
                if(cur.Left == null)
                {
                    cur.Left = new Node(val);
                    break;
                }
                else
                {
                    cur = cur.Left;
                }
            }
            else
            {
                break;
            }
        }
    }
   
   
    static Node NearestCommonAncestor(int i, int j)
    {
        int smaller = i < j ? i : j, 
           larger = i + j - smaller;
        return NearestCommonAncestor(smaller, larger, _root);
    }
   
    static Node NearestCommonAncestor(int i, int j, Node root)
    {
        if(root == null)
            return null;
        else if(root.Val < i)
            return NearestCommonAncestor(i, j, root.Right);
        else if(root.Val > j)
            return NearestCommonAncestor(i, j, root.Left);
        else
            return root;
    }

    static int DistanceToNode(Node start, int val)
    {
        int d = 0;
        for(Node cur = start; ; )
        {
            if(cur == null)
                return -1;
            else if(cur.Val < val)
            {
                cur = cur.Right;
                d += 1;
            }
            else if(cur.Val > val)
            {
                cur = cur.Left;
                d += 1;
            }
            else
                break;
        }
        return d;
    }
   
    static int DistanceBetweenNodes(int i, int j)
    {
        Node nca = NearestCommonAncestor(i, j);
        if(nca == null)
            return -1;
        int di = DistanceToNode(nca, i);
        int dj = DistanceToNode(nca, j);
        if(di == -1 || dj == -1)
            return -1;
        return di + dj;
    }
   
    public static void Main(String[] args)
    {
        int[] vals = { 2, 1, 5, 3, 8 };
        foreach(int i in vals)
            AddToTree(i);
        /*
                Now the tree should look like 
               
                2
              / \
             1   5
                / \
                3   8
                             
        */
        IEnumerable<string> results = 
            from x in vals
            from y in vals
            select string.Format
            (
                "Distance between {0} and {1} is {2}",
                x, y, DistanceBetweenNodes(x,y)
            );
        foreach(string message in results)
            Console.WriteLine(message);
    }
}
 
Technology news on Phys.org
  • #2
Ah, I just realized that I could get rid of the

Code:
        if(nca == null)
            return -1;

line and it would run the same.
 
  • #3
You might want to tell us what this code is supposed to do.
 
  • #4
Here's my code review:
Without really studying your code, it seems like the overall organization and algorithm may be ok. That being said, it is not nearly ready for code review.
You need MANY more comments. At the top, give a top level summary of what the class is for. Each method needs a description of what it does, definitions of the inputs and outputs, any special comments about algorithms used. The class name "Solution" is totally inadequate for identifying what this stuff is. Anything tricky should have a comment about what is going on. Many variable names should be more descriptive of what they are.
I hate being so harsh, but I would not accept this code if someone gave it to me. I wouldn't even try to figure it out.

PS. Keep in mind that a company will have programs with millions of lines of code. And a programmer will spend most of his time diving into the middle of code that he did not program and doesn't have the time to figure out the whole thing with no help. Try to make your code such that another programmer can do that. You will be on the receiving end of code like that.

PPS. It is good practice to format your comments so that a documentation generator like Doxygen can use the top level ones you want it to use and will ignore the lower level detail ones.
 
Last edited:

Related to Can someone code review my "Distance between nodes in a BT"?

1. What is the purpose of calculating the distance between nodes in a Binary Tree?

The distance between nodes in a Binary Tree is a measure of how many edges are present between two given nodes. It helps us understand the relationship between different nodes in a tree and is useful in various tree-based algorithms.

2. How is the distance between nodes calculated in a Binary Tree?

The distance between nodes in a Binary Tree is calculated by finding the shortest path between the two nodes. This can be done using various algorithms such as Breadth-First Search or Depth-First Search. The distance is equal to the number of edges traversed to reach from one node to the other.

3. Can the distance between nodes be negative in a Binary Tree?

No, the distance between nodes in a Binary Tree cannot be negative as it is a measure of the number of edges between two nodes. Since the minimum number of edges between any two nodes is 0, the distance will always be a positive integer.

4. What is the time complexity for calculating the distance between nodes in a Binary Tree?

The time complexity for calculating the distance between nodes in a Binary Tree depends on the algorithm used. In general, it can range from O(log n) to O(n) where n is the number of nodes in the tree. This makes it an efficient operation compared to other tree-based operations.

5. Are there any applications of calculating the distance between nodes in a Binary Tree?

Yes, there are various applications of calculating the distance between nodes in a Binary Tree. It is used in graph theory, network routing algorithms, and in the creation of hierarchical data structures. It is also useful in finding the nearest common ancestor of two nodes in a tree.

Similar threads

  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
8
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
3
Views
3K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
2
Replies
55
Views
4K
  • Programming and Computer Science
Replies
2
Views
2K
  • Programming and Computer Science
Replies
3
Views
2K
  • Programming and Computer Science
Replies
13
Views
4K
Back
Top