Engaged Employer

## Interview Question

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