Interview Question

Game Programmer Interview

-San Francisco, CA

Zynga

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

Answer

Interview Answers

5 Answers

2

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

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

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

0

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

Anonymous on

0

how about bfs?

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.