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
Answer

Interview Answer

5 Answers

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

how about bfs?

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