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?

algorithm, recursive algorithm, c++ programming

Interview Answer

5 Answers


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

how about bfs?

Anonymous on Feb 17, 2012

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

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

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 > 0xFFFF ? 0 : 1) >= result;

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

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

tmp= (val > 0x3 ? 0 : 1) >= tmp;
result |= tmp;
result |= (val >> 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.