CODEWITHSUNDEEP
javaalgorithmdata-structurestreebinary-tree
John Doe
John Doe

Reputation: 2924

Finding the height of a binary tree

I wrote the following code for finding the height of the binary tree, this is wrong, its failing the test cases, but why it is wrong, how to prove logically that this is wrong?

// WRONG CODE

public static int height(Node root) {
          if(root != null){
            if(root.left != null && root.right != null){   
              return Math.max(height(root.left), height(root.right)) + 1;
            }else if(root.left != null){
               return height(root.left);  
            }else{
               return height(root.right);
            } 
          }
        return 0;  
    }

Whereas this following code is right!!

//RIGHT WORKING CODE

public static int height(Node root) {
    if(root != null){
        if(root.left != null || root.right != null){   
          return Math.max(height(root.left), height(root.right)) + 1;
        }
      }
    return 0;  
}

What is the big difference between the two codes that makes one of them right and other the wrong one?

For clarity the class code for the Node is added here.

class Node {
    Node left;
    Node right;
    int data;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

And this is the logic to insert a node into the binary tree.

public static Node insert(Node root, int data) {
    if(root == null) {
        return new Node(data);
    } else {
        Node cur;
        if(data <= root.data) {
            cur = insert(root.left, data);
            root.left = cur;
        } else {
            cur = insert(root.right, data);
            root.right = cur;
        }
        return root;
    }

Upvotes: 0

Views: 484

Answers (1)

Willis Blackburn
Willis Blackburn

Reputation: 8204

In the second and third cases (just a left node, or just a right node) you're not adding one to account for the node you're currently on.

By the way your code also has a potential bug, in that it's possible for both left and right to be null. Your height function can handle null so really none of this checking is necessary, except for the check on the first line of the height function itself. But if it's important to check for null in the second case, then you should check for null in the third case too.

Upvotes: 4

Related Questions