Facebook

  www.facebook.com
Work in HR? Unlock Free Profile

Facebook Software Engineer Interview Question

I interviewed in Palo Alto, CA and was asked:
"Find the minimum depth of binary search tree"
Tags: binary tree c
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 1,067 Facebook Interview Reviews

Answers & Comments

2
of 5
votes
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
6
of 6
votes
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
of 5
votes
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
- mohammadkotb on Jan 3, 2011
0
of 0
votes
public int minDepth(Node root) {
  Map<Node, Integer> depthMap = new HashMap<Node, Integer>();
  depthMap.put(root, 0);
  List<Node> toVisit = new ArrayList<Node>();
  toVisit.add(root);
  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);
        toVisit.add(curr.getLeft());
      }
      if(curr.getRight() != null) {
        depthMap.put(curr.getRight(), depthMap.get(curr) + 1);
        toVisit.add(curr.getRigth());
      }
    }
  }

  return -1; // not good
}
- Viet Nguyen on Jan 31, 2011
0
of 0
votes
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
of 0
votes
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
of 0
votes
Someone said you need to pass 3 questions to be qualified to on-site...
- Anonymous on Feb 22, 2011
4
of 5
votes
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;
        }
        Queue<Node> queue = new LinkedList();
        queue.add(root);
        queue.add(new Sentinel());
        int depth = 1;
        while(!queue.isEmpty()){
            Node current = queue.poll();
            if (!(current instanceof Sentinel)) {
                if (current.left==null && current.right==null) {
                    break;
                }
                else {
                    if (current.left!=null) queue.add(current.left);
                    if (current.right!=null) queue.add(current.right);
                }
            }
            else {
                depth++;
                if (!queue.isEmpty()) {
                    queue.add(new Sentinel());
                }
            }
        }
        return depth;
    }
- cindiana on Apr 22, 2011
1
of 1
vote
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
of 0
votes
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);

        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) {
                q.add(n.left);
                enqueuedNum++;
            }

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

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

            if (lastLevelNum == visitedNum) {
                lastLevelNum = enqueuedNum;
                minDepth++;
            }
        }
    }
}
- Anonymous on May 19, 2012

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords that help categorize interview questions that have something in common.