Trees in JavaScript: nodes, traversals, and the foundation for BSTs and heaps. Clear, practical Node.js examples throughout.
Jonathan Juliani
Sr Software Engineer - Full Stack · WithClutch Inc. | Juliani Tecnologia
DOM, filesystems, nested menus — all trees: a root, children, no cycles (in theory). Foundation for BST (ep. 12), heaps (ep. 9), and tries (ep. 13).
TreeNode with left / rightPrerequisites: queues (ep. 5).
left, right, and traversalsTrees are one of the most fundamental and powerful data structures, with trees we can organize data in a hierarchically. This type of structure can help us optimize data processing in general, from manipulating file systems to performing quick searches and also sorting.
Let's see the basic implementation of a tree in NodeJS/Javascript and the pros of using this structure.
The basic structure of a tree is made up of nodes, with a single node at the top (the root node). Each node can have child nodes, but only one parent, except the root, which has no parent. Seems like we are already complicating things up, right?
The depth of a node is measured by the number of edges between the node and the root. Trees are ideal for representing hierarchical relationships and for performing efficient searches and insertions.
So the basic implementation of a Tree will start with a object that will represent the "nodes" and another object to represent the actual tree.
class TreeNode {
constructor(value) {
this.value = value
this.left = null // left leaf
this.right = null // right leaf
}
}
class BinaryTree {
constructor() {
this.root = null
}
// Here we can put the functions to insert, print, etc
}Now we can create the insert function:
insert(value) {
//check for params if needed
const node = new TreeNode(value);
if (this.root === null) {
this.root = node;
} else {
let current = this.root;
while (true) {
if (value < current.value) {
if (!current.left) {
current.left = node;
return this;
}
current = current.left;
} else {
if (!current.right) {
current.right = node;
return this;
}
current = current.right;
}
}
}
}That's basically it. We have a tree with a insert function already working, one thing we can do now is "print" the tree values:
print() {
return console.log(JSON.stringify(this.__traverse(this.root)));
}
__traverse = (node) => {
const tree = { value: node.value };
tree.left = node.left === null ? null : this.__traverse(node.left);
tree.right = node.right === null ? null : this.__traverse(node.right);
return tree;
};What is this
__traversething?
So, "traverse" is basically a function name, it represents the action of reading a node and getting to the next node, this "movement" from node A to node B is what we call traverse.
Now let's insert some values and run our Tree:
const tree = new BinaryTree()
tree.insert(9)
tree.insert(4)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
tree.insert(6)
tree.lookup(6)
tree.print()If you done it right, you should be seeing something like:
{
"value": 9,
"left": {
"value": 4,
"left": { "value": 1, "left": null, "right": null },
"right": { "value": 6, "left": null, "right": null }
},
"right": {
"value": 20,
"left": { "value": 15, "left": null, "right": null },
"right": { "value": 170, "left": null, "right": null }
}
}A note here: we implemented a binary tree, so the elements that are bigger than the root node will go to the right, and the smaller ones to the left. There are other types of trees that we will explore in other posts, if you want a challange you can change to insert objects and see what happens!!
Inserting sorted data 1,2,3,... into a naive BST-shaped insert turns the tree into a linked list — O(n).
Deep recursive walks can hit Maximum call stack size exceeded — use an explicit stack for very tall trees.
| Idea | Detail |
|---|---|
| Binary tree | At most two children |
| BST rule | left < node < right |
| Next | ep. 7 graphs, ep. 12 BST |
Do you implement trees from scratch at work, or mostly recognise hierarchical problems? Report bugs in the JSON tree example if you find them.
Get architecture and performance notes in your inbox. Same list as the timed prompt—subscribe here anytime.
