Common Binary Tree Questions Java

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) {
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;
}
}
}``````