Instantly share code, notes, and snippets.

# lazywithclass/blog-post.md

Created February 20, 2017 02:18
Show Gist options
• Save lazywithclass/7c416e0e8176c5612915a3012fc49538 to your computer and use it in GitHub Desktop.
Breadth first and depth first, same algorithm different data structure

## Breadth first and depth first, same algorithm different data structure

I am studying data structures in my free time, because I feel like it's a huge gap in my skillset; while I was going through a hacker rank exercise I thought if it was possible to read a binary tree in BFS and DFS just by changing the helper data structure.

Don't take this as correct for granted (and it might as well sound obvious to you) as I'm still studying and there might be errors, in which case please do let me know!

### The idea

BFS uses a queue while DFS uses a stack, provided the two datastructures have the same names we can change them without affecting the code.

### Example

This is the example data structure, a simple binary tree:

```//        1
//    2       3
//  4       5   6

var root = {
data: 1,
left: {
data: 2,
left: { data: 4 }
},
right: {
data: 3,
left: { data: 5 },
right: { data: 6 }
}
};```

### Data structures

For both I've provided a `addChildren` function just because I wanted the results to be always printed left to right, which does not happen if you don't invert the `add`s for the stack.

#### Queue

A queue `add`s items at the head and `get`s them from the tail

```var array = [];
var queue = {
array.unshift(o);
},
},
get: function() {
return array.pop();
},
length: function() {
return array.length;
}
};```

#### Stack

A stack `add`s element at the head and `get`s them from the tail

```var array = [];
var stack = {
array.push(node);
},
},
get: function() {
return array.pop();
},
length: function() {
return array.length;
}
};```

### Implementation

Given the following implementation we can pass either a stack or a queue as the helper data structure and get the proper results.

```function search(root, datastructure) {
while (datastructure.length() > 0) {
var node = datastructure.get();
if (!node.visited) {
console.log(node.data);
node.visited = true;
}
}
}```

To test it you could run the following

```console.log('queue, bfs');
search(root, require('./queue'));```

or

```console.log('stack, dfs');
search(root, require('./stack'));```