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