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

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

isn't this? int mindepth(node* root) { if(root==NULL) return 0; return 1 + min(mindepth(root->left),mindepth(root->right)); }

public class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } Queue<div>q = new LinkedList<div>(); 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++; } } } }</div></div>

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...

public int minDepth(Node root) { Map depthMap = new HashMap(); depthMap.put(root, 0); List toVisit = new ArrayList(); 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!