## Interview Question

Software Engineer Interview Palo Alto, CA

## Find the minimum depth of binary search tree

## Interview Answer

10 Answers

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?

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

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

}

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!

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!

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

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;

}

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

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

}

}

}

}

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

isn't this?

int mindepth(node* root)

{

if(root==NULL) return 0;

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

}