View profile

Day #14: Binary Tree Traversal: Pre-Order, Post-Order, In-Order, BFS

Puppy Nomadic
Puppy Nomadic
Today we continued pair programming to implement data structures. My partner Kevin and I focused on writing methods for traversing binary trees: pre-order, post-order, in-order, and breadth first search.

Implementing a Binary Tree Recursively
Rather than creating a Binary Tree object with a root node pointer, and a Node class with value / left / right pointers, our exercise today was to treat each binary tree node as its own binary tree, and write all methods recursively.
Depth-First Search
There are three methods for depth-first search, to go down all the child nodes of a binary tree node in one direction, before traversing across to other sibling nodes. With depth-first search, you’ll never have more than the height of the tree in memory.
Pre-Order Search: Root - Left - Right
BinarySearchTree.prototype.depthFirstPre = function(callback) {
callback(this.value);
if(this.left) {
this.left.depthFirstPre(callback);
}
if(this.right) {
this.right.depthFirstPre(callback);
}
return;
};
In Order Search: Left - Root - Right
Post Order Search: Left - Right - Root
We implemented in-order and post-order in a similar way to pre-order.
Breadth-First Search
Breadth-First Search is extremely memory-intensive. It requires holding all the child nodes of a given level in a queue and traversing through them after each previous level is done. With breadth-first search, you could have all the nodes in the bottom level in memory, which means it increase exponentially as you traverse the height.
BinarySearchTree.prototype.breadthFirst = function(callback) {
let storage = [this];
let currentNode;
while (storage.length) {
currentNode = storage[0];
if (currentNode.left) {
storage.push(currentNode.left);
}
if (currentNode.right) {
storage.push(currentNode.right);
}
callback(storage.shift().value);
}
};
Memory Usage: BFS vs DFS
BFS uses O(branchingFactor^maxDepth) or O(maxWidth) memory, where-as DFS only uses O(maxDepth).
Breadth First Search
Depth-First Search
Additional Links and Resources
Binary Search Tree in JavaScript. Binary search tree, as shown in its… | by Gulgina Arkin | The Startup | Medium
Did you enjoy this issue? Yes No
Puppy Nomadic
Puppy Nomadic @puppynomadic

Let's pull each other up by our Bootstrap.js 🪴 👩🏻‍💻 🦮

=== Journey of software craftsmanship ===

{"Formerly": ["nonprofit community organizer", "teacher", "researcher", "government director"],
"Future": ["software engineer", "web3 dev", "developer advocate", "technical program manager"]
}

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.