# Traversing a Tree Structure with Breadth First Search

A binary search tree provides many advantages to other data storage methods, offering O(log n) time complexity by organizing the data in an ordered pattern. Depending on a value comparison between the parent node and the child node, the data structure determines the placement of the node on the tree after initially determining whether the value being inserted is less than or greater than the root node. When searching for a node's value, half of the data structure is ignored while this value comparison continues down the tree and repeats at every node.

The structure also provides numerous methods to traverse the tree in a specific order. The traversal pattern familiar to web developers is the depth first search method, which traverses down a branch until there are no more leaves on that branch. This pattern can be represented simply in code using Douglas Crockford's WalkTheDom function, found in the excellent book Javascript: The Good Parts.

```
var walkDOM = function (node,func) {
func(node);
node = node.firstChild;
while(node) {
walkDOM(node,func);
node = node.nextSibling;
}
};
```

However, the Breadth First Search pattern also offers a way to move through the Binary Seach Tree, or any tree, depending on your intent. This method separates the tree structure into levels, with each child of a node representing a new level:

While the Walk the Dom method has many applications for web developers, the breadth first search pattern is less intuitive to programmers. But it does have some use, such as accessing nodes along the same plane, or rank, like military or organizational hierarchies. Additionally, if you know that the node you are looking for is relatively close to the beginning node, time spent moving deeper along a branch is wasted when the solution is several layers up.

Depth First Search traversals can commonly be performed with the use of a recursive function call; if there is a subordinate element, execute the function on that element, until the most distant element from the start point is acted on. Once the end of the branch has been reached, other branches are accessed.

The Breadth First Search traversal is similar, in that the same approach can be taken. We want to do something to the tree structure as long as our base case isn't met. We can utilize a common queue (First In, First Out) structure to traverse the tree.

```
function breadthFirstSearch(callback) {
var nodeList = [this],
node = nodeList[0];
while (node) {
if (node.left.value !== undefined) nodeList.unshift(node.left);
if (node.right.value !== undefined) nodeList.unshift(node.right);
callback(nodeList.pop());
node = nodeList[nodeList.length - 1];
}
}
```

The code for a traditional tree is less elegant but accomplishes the same thing. The array will never contain more than the parent node and its children, which allows traversal of the data structure without creating an array with too many objects.

```
function breadthFirstSearch(callback) {
var nodeList = [this],
node = nodeList[0];
while (node) {
if (node.children.length > 0) {
for (var i = 0; i < node.children.length; i++) {
nodeList.unshift(node.children[i])
}
}
callback(nodeList.pop());
node = nodeList[nodeList.length - 1];
}
```