## Maximum Depth of Binary Tree

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.