Finding Height Of A Binary Tree

Height of a Binary tree is the length of the path form its root node to its farthest leaf node or we can say the longest path from root node to any of the leaf node (here path means the link between two nodes).
For example - height of the binary tree in the figure given below (Fig 1.0) is 3. As we can see that this tree has two leaf nodes 3 and 12 but node leaf 3 is the farthest from the root and length of the path between 10 (root node) and 3 (farthest leaf node) is 3 hence height of the tree is 3.
From above example comes our algorithm to calculate the height of the tree, we will calculate the height of the left and right subtree of each node recursively and consider the height of the tree including the root node - adding one to the greater of the two heights (left and right subtree heights).

Fig 1.0

Implementation - In below code we have implementaed a custom BST with a public method getHeight() which internaly calls another private method getHeight() passing root of the tree as argument to calculate and return height of the tree. These two methods are highlight in the code.

package ds.tree;

public class BStree {

	private Node root;

	public Node getRoot() {
		return root;
	}

	public BStree(int rootData) {
		this.root = new Node(rootData);
	}
	
	public BStree(Node root) {
		this.root = root;
	}

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

		public Node(int data) {
			this.data = data;
		}
	}
    
    

    public int getHeight() {
		return getHeight(this.root);
	}
	
	private int getHeight(Node root) {
		if(root == null)
			return -1;
		int lHeight = getHeight(root.left);
		int rHeight = getHeight(root.right);
		
		if(lHeight > rHeight)
			return lHeight + 1;
		else
			return rHeight + 1;
	}
    

	public void insert(int data) {
		Node nNode = new Node(data);
		
		Node root = this.root;
		Node nodeB = null;
		while (root != null) {
			nodeB = root;
			if (root.data > data) {
				root = root.left;
			} else {
				root = root.right;
			}
		}
		if(data < nodeB.data)
			nodeB.left = nNode;
		else
			nodeB.right = nNode; 
	}
}

Main method - Lets take the example of the BST given in the figure above and print its height.

package ds.tree;

public class BtreeMain {
	
	public static void main(String[] args) {
		BStree bst = new BStree(10);
		bst.insert(14);
		bst.insert(2);
		bst.insert(9);
		bst.insert(12);
		bst.insert(3);
		
		System.out.println("Height of BST is - " + bst.getHeight());
	}
}

Output -

Height of BST is - 3