This is a basic algorithm for finding the depth of a binary tree.

How it Works

The depth of a binary tree is defined as being the level of its deepest node. So, for example, a tree that is just a root has depth = 1. A tree whose root has a left node and a right node has depth = 2 as either node is just one from the root. A tree whose root has a left node, that also has its own left node has depth = 3, and so on. Only the deepest path is relevant in determining the tree depth.

The algorithm that we use to get the depth is very concise. All it does is recursively traverse the tree while tracking the count at each level. The result of each level is the maximum depth (count) between the left and right sub-trees. So, at the root, we start with count = 1 + max(count(left-subtree), count(right-subtree)). We continue this, adding one at each level, until we get to the leaf nodes where we get the final counts. Since we only retain the maximum count at each level, by the time the original call at which started with the root node returns, we have only the maximum count (depth) of the tree left.

Sample Implementation

Here is a sample implementation. You may double-click to copy the contents of the sample into your IDE so that you may play with it in a debugger to learn more.

 public class BinaryTreeDepth {

     //A simple class to represent a node in the binary tree.
     private static class Node {
         public Node(int v) { this.value = v; }
         int value;
         Node left;
         Node right;
     }

     //This main method demonstrates the algorithm's use.
     public static void main(String[] args) {

         //Create a tree where the largest depth is 5 on the left.
         Node root = new Node(5);
         root.left = new Node(3);
         root.left.right = new Node(4);
         root.left.left = new Node(2);
         root.left.left.left = new Node(1);
         root.left.left.left.left = new Node(0);

         //We'll give the right side maximum depth 3.
         root.right = new Node(7);
         root.right.left = new Node(6);
         root.right.right = new Node(8);
         root.right.right = new Node(9);

         //Print the depth of the tree.
         System.out.println(depth(root));
         System.out.println(isBalanced(root));
     }

     //This a recursive function for finding the depth of a tree.
     //The trick here is that as we recurse down to the next level
     //of the tree in each case, we add 1 to the depth.  We also
     //make sure that we only track the maximum depth between the
     //two subtrees as that is all we care about.
     public static int depth(Node root) {
         if (root == null) return 0;
         return 1 + Math.max(depth(root.left), depth(root.right));
     }
 }