Common Binary Tree Questions

The Node class is defined as follows:

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

Height of the binary tree

public static int height(Node root) {
    if(root == null){
        return -1;
    }else{
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if(leftHeight > rightHeight)
            return leftHeight+1;
        else
            return rightHeight+1;
    }
}

Check If binary Tree is BST

Binary search tree has its node value greater than left node value and lesser than right node value.

The below code checks recursively.

boolean checkBST(Node root) {
    return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

boolean isBST(Node node, int min, int max){
    if(node == null) return true;
    else 
        return (node.data > min && node.data < max 
         && isBST(node.left, min, node.data)
         && isBST(node.right, node.data, max));       

}

Alternate approach. This passes for a number of cases. But fails for few. So avoid using this technique.

int lastValue = Integer.MIN_VALUE;
boolean checkBST(Node root) {
    if(root == null) return true;
    //leaf element will return true. which will cause this if to fail
    if(!checkBST(root.left)) return false;
    //last element data can't be less than MIN_VALUE
    if(root.data < lastValue) return false;
    //leaf node becomes last value
    lastValue = root.data;
    return checkBST(root.right);   
}

Least Common Ancestor

public static Node lca(Node root, int v1, int v2) {
        // Write your code here.
        if (root == null) {
           return null;
       }

       if (root.data == v1 || root.data == v2) {
           return root;
       }else{
           Node leftLca = lca(root.left, v1, v2);
           Node rightLca = lca(root.right, v2, v2);

           if (leftLca != null && rightLca != null) {
              return root;
           }else if(leftLca != null){
                return leftLca;
           }else{
               return rightLca;
           }
       }
    }