At some point in your career (today?!) you will want to learn data structures. It’s not just to ace the technical interview and land your dream job. Learning data structures will help you understand how software works and improve your problemsolving skills. In this tutorial, you will implement traversal of a tree data structure in JavaScript.
Retrieval Practice

What is a tree?

What is a forest?

What is a binary tree?
What is a Tree?
The tree is a data structure composed of nodes connected by edges. In The Art of Computer Programming, Donald Knuth provides a recursive definition of trees:

there is one specially designated node called the root of the tree,
root(T)
; and… 
the remaining nodes (excluding the root) are partitioned into
m >= 0
disjoint setsT1… ™
, and each of these sets in turn is a tree.
What is a forest?
A forest is a set of trees or the nodes of a tree excluding the root.
What is a Binary Tree?
A binary tree is a type of tree where parent nodes are restricted to no more than two child nodes. Knuth defines binary trees as:
a finite set of nodes that either is empty, or consists of a root and the elements of two disjoint binary trees called the left and right subtrees of the root.
What Problem(s) Do Trees Solve?
 Binary trees are chosen over other more primary data structures because you can search a binary tree very quickly (as opposed to a linked list, for example) and you can quickly insert and delete data from a binary tree (as opposed to an array).
Implementation of a Binary Search Tree Data Structure in JavaScript
Below is our implementation of a binary search tree in JavaScript. If you are just joining us, you may want to start with the previous article JavaScript Tree Data Structure.
class Node {
constructor(data, left, right) {
this.data = data;
this.left = left  null;
this.right = right  null;
}
}
class Tree {
constructor() {
this.root = null;
}
insert(data) {
const node = new Node(data, null, null);
if (this.root === null) {
this.root = node;
return;
}
let current = this.root;
let parent;
while(current) {
parent = current;
if (data <= current.data) {
current = current.left;
if (current === null) {
parent.left = node;
}
} else {
current = current.right;
if (current === null) {
parent.right = node;
}
}
}
}
}
const tree = new Tree();
tree.insert(64);
tree.insert(127);
tree.insert(0);
tree.insert(32);
tree.insert(256);
If we log our tree
, we get:
Tree {
root: Node {
data: 64,
left: Node { data: 0, left: null, right: [Node] },
right: Node { data: 127, left: null, right: [Node] }
}
}
What is Tree Traversal?
According to Wikipedia, tree traversal (AKA walking the tree) is:
refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once.
There are three standard functions for traversing a tree:

inorder

preorder

postorder
Each of these is considered depthfirst search, or DFS, because we traverse a branch to its furthest depth before moving on to the next branch. This is in contrast to breadthfirst search, or BFS, which, you guessed it, traverses all of the nodes on a level before going deeper into the tree.
Let’s start in order with inorder.
Tree Traversal InOrder
Recall that one of the defining features of a BTS is the storage of nodes with lower values to the left and higher values to the right. An inorder traversal returns the values of nodes in ascending order.
You will see a lot of examples of inorder traversal that simply log the values from within, like this:
traverseInOrder(node) {
if (node !== null) {
this.traverseInOrder(node.left);
console.log(node.data);
this.traverseInOrder(node.right);
}
}
We declare a method traverseInOrder
and pass it a node
argument. If the node
is not equal to null
, we recursively call traverseInOrder
and pass it the left child. We then log the value stored in node.data
and recursively call traverseInOrder
, passing it the right child.
Why do we sandwich the log between recursive calls?
Because we want to return values in order, or ascending from smallest to largest. To get all of the smaller values, we need to traverse the left nodes first, then the right nodes. If this doesn’t make sense, don’t worry, it will click when we look at the pre and postorder below.
Using our example above, tree.traverseInOrder(tree.root);
will return:
[ 0, 32, 64, 127, 256 ]
This is a great proof of concept. The method works! But you can’t do anything with a logged value except observe it. We need our method to return the values stored in our tree. But, what happens if we plug a return value in between our recursive calls to this.traverseInOrder()
?
Yep. Our method will exit before we traverse the right nodes.
How do we solve this problem?
The solution is dynamic! We need to store, or cache, the return value of each call to this.traverseInOrder()
.
How do we do that?
We can pass an array up and down the call stack and push
the node.data
at each call into it.
traverseInOrder(node = this.root, memo = []) {
if (node !== null) {
this.traverseInOrder(node.left, memo);
memo.push(node.data);
this.traverseInOrder(node.right, memo);
}
return memo;
}
This is an example of memoization. If you want to learn more, check out my article What is Dynamic Programming? Memoization and Tabulation.
📝 Note that we set the node
parameter to default to this.root
.
Our tree now looks like this:
class Tree {
constructor() {
this.root = null;
}
insert(data) {
const node = new Node(data, null, null);
if (this.root === null) {
this.root = node;
return;
}
let current = this.root;
let parent;
while(current) {
parent = current;
if (data <= current.data) {
current = current.left;
if (current === null) {
parent.left = node;
}
} else {
current = current.right;
if (current === null) {
parent.right = node;
}
}
}
}
traverseInOrder(node = this.root, memo = []) {
if (node !== null) {
this.traverseInOrder(node.left, memo);
memo.push(node.data);
this.traverseInOrder(node.right, memo);
}
return memo;
}
}
Tree Traversal PreOrder
A preorder traversal returns the values of nodes beginning with the root and proceeding down the left branch of each subtree, then followed by the right branch of each subtree.
traversePreOrder(node = this.root, memo = []) {
if (node !== null) {
memo.push(node.data);
this.traverseInOrder(node.left, memo);
this.traverseInOrder(node.right, memo);
}
return memo;
}
📝 Note that traversePreOrder
differs from inorder by pushing the value in the current node
before making any recursive calls.
Our tree now looks like this:
class Tree {
constructor() {
this.root = null;
}
insert(data) {
const node = new Node(data, null, null);
if (this.root === null) {
this.root = node;
return;
}
let current = this.root;
let parent;
while(current) {
parent = current;
if (data <= current.data) {
current = current.left;
if (current === null) {
parent.left = node;
}
} else {
current = current.right;
if (current === null) {
parent.right = node;
}
}
}
}
traverseInOrder(node = this.root, memo = []) {
if (node !== null) {
this.traverseInOrder(node.left, memo);
memo.push(node.data);
this.traverseInOrder(node.right, memo);
}
return memo;
}
traversePreOrder(node = this.root, memo = []) {
if (node !== null) {
memo.push(node.data);
this.traverseInOrder(node.left, memo);
this.traverseInOrder(node.right, memo);
}
return memo;
}
}
Tree Traversal PostOrder
A postorder traversal is the inverse of preorder. It returns the values of nodes beginning with the child nodes of the left subtree, then the right branch of each subtree, ending with the root.
traversePostOrder(node = this.root, memo = []) {
if (node !== null) {
this.traverseInOrder(node.left, memo);
this.traverseInOrder(node.right, memo);
memo.push(node.data);
}
return memo;
}
📝 Note that traversePreOrder
differs from inorder and preorder by pushing the value in the current node
after making the recursive calls.
Our tree now looks like this, including our Node
class:
class Node {
constructor(data, left, right) {
this.data = data;
this.left = left  null;
this.right = right  null;
}
}
class Tree {
constructor() {
this.root = null;
}
insert(data) {
const node = new Node(data, null, null);
if (this.root === null) {
this.root = node;
return;
}
let current = this.root;
let parent;
while(current) {
parent = current;
if (data <= current.data) {
current = current.left;
if (current === null) {
parent.left = node;
}
} else {
current = current.right;
if (current === null) {
parent.right = node;
}
}
}
}
traverseInOrder(node = this.root, memo = []) {
if (node !== null) {
this.traverseInOrder(node.left, memo);
memo.push(node.data);
this.traverseInOrder(node.right, memo);
}
return memo;
}
traversePreOrder(node = this.root, memo = []) {
if (node !== null) {
memo.push(node.data);
this.traverseInOrder(node.left, memo);
this.traverseInOrder(node.right, memo);
}
return memo;
}
traversePostOrder(node = this.root, memo = []) {
if (node !== null) {
this.traverseInOrder(node.left, memo);
this.traverseInOrder(node.right, memo);
memo.push(node.data);
}
return memo;
}
}
Big O & Tree Data Structures
The access, search, insertion, and deletion methods of a binary search tree are all O(n) due to the use of iteration. Average case, though, is O(log n) because we are continually dividing our operations as we execute a method.
Learn JavaScript Tree Data Structure
In this tutorial you learned how to implement inorder, preorder, and postorder traversal of a tree data structure in JavaScript. We’re not done, though. In the next tutorial we’ll implement our other methods.