The height of a Binary Tree is a number of edges between the tree's root and its furthest leaf. For example, the height of the following binary tree is 2

A tree consisting of only a single node has a height of 0

Problem

  • Given a binary tree

  • Write an algorithm to find height or maximum depth of it

Approach

  • For every parent node in a binary tree 
height(parenNode) = max(height(leftChild), height(rightChild)) + 1
  • Run the above function recursively for all nodes in the given tree, starting from root node
import com.hellokoding.datastructure.BSTByLinkedList;

public class BinaryTreeHeight extends BSTByLinkedList {  
    public int height(Node node) {
        if (node == null) return -1;

        return Math.max(height(node.left), height(node.right)) + 1;
    }

    public static void main(String[] args) {
        BinaryTreeHeight tree = new BinaryTreeHeight();
        tree.insert(7);
        tree.insert(2);
        tree.insert(3);
        tree.insert(1);
        tree.insert(9);

        tree.inTraversal(tree.root);
        System.out.println(tree.height(tree.root));
    }
}

BSTByLinkedList is defined in Binary Search Tree Data Structure

Algorithm