Facebook Interview Question: Find the minimum depth of bin... | Glassdoor

## Interview Question

Software Engineer Interview Palo Alto, CA

# Find the minimum depth of binary search tree

Tags:
binary tree c

4

isn't this?

int mindepth(node* root)
{
if(root==NULL) return 0;

return 1 + min(mindepth(root->left),mindepth(root->right));
}

Anonymous on Dec 16, 2010
8

You wouldn't get an on-site interview with this answer.
Your code is not optimal, although it looks short.
Here is the trick: you don't have to traverse entire tree to find out the minimum.

think about this example. L side of the root node has only one item, so the deep is 1, R side of the root has one million items. Why do you have to traverse through all one million nodes, if you can get the min from the L side right away?

Anonymous on Dec 16, 2010
5

It can be solved using the previous recursive code
and also can be solved using Breadth First Traversal, by starting the traversal from the root of the tree, and when reach a leaf then this is the min depth return the number of steps from the root to this leaf

0

public int minDepth(Node root) {
Map depthMap = new HashMap();
depthMap.put(root, 0);
List toVisit = new ArrayList();
while(!toVisit.isEmpty()) {
Node curr = toVisit.remove(0);
if(curr.getLeft() == null && curr.getRight() == null) {
// first leaf node is the minimum depth
return depthMap.get(curr);
} else {
if(curr.getLeft() != null) {
depthMap.put(curr.getLeft, depthMap.get(curr) + 1);
}
if(curr.getRight() != null) {
depthMap.put(curr.getRight(), depthMap.get(curr) + 1);
}
}
}

return -1; // not good
}

Viet Nguyen on Jan 31, 2011
0

use a BFS. And use int used and int inquery. And the sum = used+inquery to identify if current node's level. It is binary tree so it has the property of the 2^(n+1)-1! node for full tree. And I think the Standard BFS is to use a query to keep everything. One problem is that ur query will grow big very fast!

pz on Feb 13, 2011
0

use a BFS. And use int used and int inquery. And the sum = used+inquery to identify if current node's level. It is binary tree so it has the property of the 2^(n+1)-1! node for full tree. And I think the Standard BFS is to use a query to keep everything. One problem is that ur query will grow big very fast!

pz on Feb 13, 2011
0

Someone said you need to pass 3 questions to be qualified to on-site...

Anonymous on Feb 22, 2011
5

Use BFS to iterate the tree, keep track of the "level" you're currently at.
When a childless node shows up, return the level number.
Code:
public static int MinDepth(Node root) {
if (root==null) {
return 0;
}
int depth = 1;
while(!queue.isEmpty()){
Node current = queue.poll();
if (!(current instanceof Sentinel)) {
if (current.left==null && current.right==null) {
break;
}
else {
}
}
else {
depth++;
if (!queue.isEmpty()) {
}
}
}
return depth;
}

cindiana on Apr 22, 2011
1

void mindepth(node* cur, int curdepth, int& best) {
if(curdepth >= best) return;
if(cur == null) {
best = curdepth;
return;
}
mindepth(cur->left, curdepth + 1, best);
mindepth(cur->right, curdepth +1, best);
}

best = inf;
mindepth(root, 0, best);

cr07 on Aug 28, 2011
0

public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}

int enqueuedNum = 1;
int visitedNum = 0;
int lastLevelNum = 1;

// initialized to be 1, whichever child tree node is null, then finish
// the operation and return the current minDepth
int minDepth = 1;

while (true) {
TreeNode n = q.poll();
visitedNum++;

if (n.left != null) {
enqueuedNum++;
}

if (n.right != null) {
enqueuedNum++;
}

if (n.left == null || n.right == null) {
return minDepth;
}

if (lastLevelNum == visitedNum) {
lastLevelNum = enqueuedNum;
minDepth++;
}
}
}
}</div></div>

Anonymous on May 19, 2012