Maximum Depth of Binary Tree

08 Aug 2010. comments

Tree data structures are great for storing data in a way that makes lookup access based on criteria efficient. In order to lookup data in a tree you need to traverse it and so this kind of thing tends to come up a lot in CS questions or interviews.

A binary tree stores data such that all the values less than the value in a node are stored down the left link node, and all the values greater than the value in a node are stored down the right link in the node. This has the effect of making the data sorted as you traverse it, and might look something like this:

    10
   /  \
  5    15
 / \    \
2   7    17

Lets look at how to traverse a binary tree and calculate the maximum depth of its branches while we are at it:

class BinaryTree {

  public int getMaxDepth() {
    return getMaxDepth(this.root);
  }

  private int getMaxDepth(Node node)  
  {  
    if(node == null) {
      // traversed off the end of a leaf,
      // so nothing here to add
      return 0;
    }

    // count this node (the 1) plus whatever comes from
    // recursively traversing left and right
    int leftDepth = 1 + getMaxDepth(node.left);  
    int rightDepth = 1 + getMaxDepth(node.right);

    // the side (left or right) with highest value is deepest
    return Math.max(leftDepth, rightDepth);
  }

}

This kind of traversal is a “depth-first” traversal because you descend all the way left as much as possible before coming back up to check down the right side of nodes.

comments

Tagged: algorithms recursion Katas interview

2017 Ben Lakey

The words here do not reflect those of my employer.