Interview Question

Software Engineer Interview Palo Alto, CA

Find the minimum depth of binary search tree

Tags:
binary tree c
Answer

Interview Answer

10 Answers

2

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

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

mohammadkotb on Jan 3, 2011
0

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

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
4

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

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;
        }

        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

Add Answers or Comments

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