Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Can someone code review my "Distance between nodes in a BT"?

Tags:
  1. Feb 3, 2017 #1
    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 (Text):

    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);
        }
    }
     
     
  2. jcsd
  3. Feb 3, 2017 #2
    Ah, I just realized that I could get rid of the

    Code (Text):

            if(nca == null)
                return -1;
     
    line and it would run the same.
     
  4. Feb 3, 2017 #3

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    You might want to tell us what this code is supposed to do.
     
  5. Feb 4, 2017 #4

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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: Feb 4, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Can someone code review my "Distance between nodes in a BT"?
Loading...