Zynga Interview Question: How do you find the max depth... | Glassdoor

## Interview Question

Game Programmer Interview San Francisco, CA

# How do you find the max depth of a binary tree?

Tags:
algorithm, recursive algorithm, c++ programming

0

I used recursion, passing the current depth to each child and returning the max value they returned plus one to the caller.

Interview Candidate on Feb 8, 2012
0

Anonymous on Feb 17, 2012
1

breadth first search will be better than the recursion method for min-depth searching, but works same as recursive in the case of finding max depth problem

Anonymous on Mar 17, 2012
1

public static int maxDepth(TreeNode root) {
if (root == null) return 0; //base case
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

Victor on Feb 24, 2013
0

This entirely depends on the implementation. It can be calculated as the integer log base 2 of the highest index of the tree. This would prevent quite a few cache misses from traversing the tree each time, and would be a fairly quick calculation using bitwise operations.

int val;// the value
int result;// the result
int tmp;

result = (val &gt; 0xFFFF ? 0 : 1) &gt;= result;

tmp= (val &gt; 0xFF ? 0 : 1) &gt;= tmp;
result |= tmp;

tmp= (val &gt; 0xF ? 0 : 1) &gt;= tmp;
result |= tmp;

tmp= (val &gt; 0x3 ? 0 : 1) &gt;= tmp;
result |= tmp;
result |= (val &gt;&gt; 1);

While this may seem like a lot, assuming the tree is small, these calculations are actually quite fast, don't involve branching, and don't require arbitrary pointers to sub-tree members.

This works best for trees that are either complete or nearly complete, however, since otherwise there will be a lot of wasted memory for indices that contain nothing.

Anonymous on Apr 11, 2015