**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.

Tagged: algorithms recursion Katas interview