## Wednesday, October 12, 2016

### Minimum Depth of a Binary Tree (Level Order Traversal)

Here is the javascript implementation:

```
var Node = function(value, left, right) {
this.value = value;
this.left = left;
this.right = right;
}

var Tree = function (root) {
this.root = root;
}

var minDepth = function (tree) {
var q = [{node: tree.root, depth:1}];
while(q.length > 0) {
var queueItem = q.pop();
if (queueItem.node.left === undefined && queueItem.node.right === undefined) {
return queueItem.depth;
}
if(queueItem.node.left !== undefined) {
q.push({node:queueItem.node.left, depth:queueItem.depth+1});
}
if(queueItem.node.right !== undefined) {
q.push({node:queueItem.node.right, depth:queueItem.depth+1});
}
}
};

var tree1 = new Tree(new Node('root'));
tree1.root.left  = new Node(1);
tree1.root.right = new Node(2);
tree1.root.left.left = new Node(3);
tree1.root.left.right = new Node(4);
tree1.root.left.left.left = new Node(6);
tree1.root.right.left = new Node(5);

console.log(minDepth(tree1));
```

It actually goes through each level. When it reaches the first leaf node, it returns the depth.

The code can be changed a little to return the minimum path, like 'root'-2-5.

```
var q = [{node: tree.root, depth:1, path:tree.root.value}];
while(q.length > 0) {
var queueItem = q.pop();
if (queueItem.node.left === undefined && queueItem.node.right === undefined) {
return queueItem.path;
}
if(queueItem.node.left !== undefined) {
q.push({node:queueItem.node.left, depth:queueItem.depth+1, path: queueItem.path +'-'+ queueItem.node.left.value});
}
if(queueItem.node.right !== undefined) {
q.push({node:queueItem.node.right, depth:queueItem.depth+1, path: queueItem.path +'-'+ queueItem.node.right.value});
}
}
```

Another question can use similar algorithm: add a node into one height balanced tree, make sure it is still a height-balanced tree.
A binary tree is height balanced if the difference between any two leaves is at most 1.
The algorithm here is to traversal each level. When the first undefined leaf found, that is the position to add the new node.

Another balanced tree is weight balanced tree. A tree is weight balanced if the diff between total nodes of the left subtree and the right subtree is at most 1.
If one more node need to be added, for height balanced tree, you can add it to right of b, or left/right of d.
But for weight balanced tree, you can only add it to left/right of d.