CODEWITHSUNDEEP
javabinary-search-tree
Pedro Moreira
Pedro Moreira

Reputation: 3

How I get a value from the furthest node from left and right

I have to find a value and the distance between the distant nodes from a bst. I've already made an method which can find the distance between both, but how I can pick a value inside the node?

  public int diameter(Node root)
   {
       // base case if tree is empty
       if (root == null)
           return 0;

       // get the height of left and right sub-trees
       int lheight = height(root.left);
       int rheight = height(root.right);

       // get the diameter of left and right sub-trees
       int ldiameter = diameter(root.left);
       int rdiameter = diameter(root.right);

       /* Return max of following three
         1) Diameter of left subtree
         2) Diameter of right subtree
         3) Height of left subtree + height of right subtree + 1
        */
       return Math.max(lheight + rheight + 1,
               Math.max(ldiameter, rdiameter));
   }

Upvotes: 0

Views: 52

Answers (1)

digital illusion
digital illusion

Reputation: 497

You should provide a reference to the furthest node; the way it is written, the function only return the distance. Please be aware that I did not compile the snippet so it may need adjustements, but just to give the idea:

    class HeightResult {
        int value;
        Node node;
    }
    
    class DiameterResult {
        int value;
        Node left;
        Node right;

        DiameterResult(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    
    public DiameterResult diameter(Node root) {
       // base case if tree is empty
       if (root == null)
           return 0;

       // get the height of left and right sub-trees
       HeightResult lheight = height(root.left);
       HeightResult rheight = height(root.right);

       // get the diameter of left and right sub-trees
       DiameterResult ldiameter = diameter(root.left);
       DiameterResult rdiameter = diameter(root.right);

       /* Return max of following three
         1) Diameter of left subtree
         2) Diameter of right subtree
         3) Height of left subtree + height of right subtree + 1
        */
       
         if (lheight.value + rheight.value + 1 >= Math.max(ldiameter.value, rdiameter.value)) {
            return new DiameterResult(lheight.value + rheight.value + 1, lheight.node, rheight.node);
         } else if (ldiameter.value >= rdiameter.value) {
            return ldiameter
         } else {
            return rdiameter;
         }
       }
   }

Upvotes: 1

Related Questions