Interview Question

Game Programmer Interview

-San Francisco, CA


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


Interview Answers

5 Answers


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


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


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


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

Anonymous on


how about bfs?

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.