In this article, we will read about the binary tree in detail. We will see how to build and traverse it in javascript.
Tree data structure
A tree is a non-linear data structure that follows some hierarchy. It is a collection of the tree nodes.
A tree node stores the information about its node value, its left child address, and right child address.
In a tree, a tree node can have multiple children.
Basic Terminology in Tree
Before diving into the code, let’s understand the basic terminologies –
- root – root is the topmost node of the tree e.g 10 is the root node in the above picture.
- siblings – The children of the parent are siblings to each other e.g 20 & 30 are siblings as both are children of node 10.
- cousins – uncles’ children are cousins to ourselves e.g node 30 is the uncle of nodes 40 & 50. Hence, nodes 40, 50, 60, and 70 are all cousins.
- height of a node – Distance from the current node to the farthest leaf e.g Height(20) = 2 because 80 is the farthest leaf from node 20.
- depth of a node – distance from the root to the node e.g depth(20) = 1
- Height of entire tree = Height of the root node
- Depth of entire tree = Height of entire tree
Binary Tree data structure
A binary tree is a tree where a tree node can have 0, 1, or 2 children at most.
How to Implement binary tree in Javascript?
function TreeNode(data) {
this.data = data;
this.left = null;
this.right = null;
}
function createTree() {
let root = new TreeNode(10);
root.left = new TreeNode(20);
root.right = new TreeNode(30);
root.left.left = new TreeNode(40);
root.left.right = new TreeNode(50);
root.right.left = new TreeNode(60);
root.right.right = new TreeNode(70);
root.left.left.right = new TreeNode(80);
return root;
}
How to traverse a binary tree?
Traversal means visiting each node of the binary tree.
There are 3 ways to traverse a binary tree –
- Preorder traversal
- Inorder traversal
- Postorder traversal
There is one more traversal Level Order traversal that is not in the scope of this article. We will read that when we solve the Left View, Right View of the binary tree, etc.
Preorder Traversal (using recursion)
It traverses the tree in the following fashion – data Left Right.
The preorder traversal for the above tree is – 10 20 40 80 50 30 60 70
function preOrder(root) {
if (root === null) return;
// print the node data
console.log(root.data);
// goto left
preOrder(root.left);
// goto right
preOrder(root.right);
}
Time Complexity: O(n) (each tree node is processed once)
Space Complexity: O(h) h is the height. of the tree.
Preorder Traversal (without recursion)
The recursive one was pretty simple but if you’re going to apply for a software developer position you might be asked to traverse the tree iteratively i.e without recursion.
We would be using one stack to remember the previous node and one array to store the answer.
To solve this, think of the preorder formula – data left right and visualize it.
Consider an example with just 3 nodes –
5
/ \
10 15
Preorder for this is – 5 10 15
Now, after processing node 5, next will be node 10. If we are using a stack and pushing the left and right node of the current node, then the right node will be pushed first and then the left one because we need to traverse left children first.
If you understood this, the implementation will be easier to understand.
function preOrder(root) {
let ans = [];
if (root === null) return ans;
// push root into stack
let stack = [root];
// loop while stack is not empty
while (stack.length) {
let cur = stack.pop();
// push the node data to ans
ans.push(cur.data);
// push right node into stack
if (cur.right) {
stack.push(cur.right);
}
// push left node into stack
// as it pushed last so will be pop first
// i.e this ensures data left right ordering
if (cur.left) {
stack.push(cur.left);
}
}
return ans;
}
Time Complexity: O(n) (each tree node is processed once)
Space Complexity: O(h) + O(n) ~= O(n)
h is the height. of the tree.
Inorder Traversal (using recursion)
It traverses the tree in the following fashion – Left data Right
The inorder traversal for the above tree is – 40 80 20 50 10 60 30 70
function inOrder(root) {
if (root === null) return;
// goto left
inOrder(root.left);
// print the node data
console.log(root.data);
// goto right
inOrder(root.right);
}
Time Complexity: O(n) (each tree node is processed once)
Space Complexity: O(h) h is the height. of the tree.
Inorder Traversal (without recursion)
Inorder formula: left data right
From the formula, we will follow below steps —
Step1: We will go to the left and keep pushing every node into the stack.
Step2: Pop the stack top element
Step3: goto right and follow Step1
function inOrder(root) {
let ans = [];
if (root === null) return ans;
// push root into stack
let stack = [];
let cur = root;
// loop while stack is not empty
while (cur || stack.length) {
// goto left
while(cur) {
stack.push(cur);
cur = cur.left;
}
// push the node data to ans
cur = stack.pop();
ans.push(cur.data);
// push right node into stack
cur = cur.right;
}
return ans.reverse();
}
Time Complexity: O(n) (each tree node is processed once)
Space Complexity: O(h) + O(n) ~= O(n)
h is the height. of the tree.
Postorder Traversal (using recursion)
It traverses the tree in the following fashion – Left Right data
The postorder traversal for the above tree is – 80 40 50 20 60 70 30 10
function postOrder(root) {
if (root === null) return;
// goto left
postOrder(root.left);
// goto right
postOrder(root.right);
// print the node data
console.log(root.data);
}
Time Complexity: O(n) (each tree node is processed once)
Space Complexity: O(h) h is the height. of the tree.
Postorder Traversal (without recursion)
Let’s think of the preorder traversal solution again. This is similar to that.
preorder formula: data left right
Now, reverse the left and right position, the formula will become data right left
And if we reverse the entire formula, the final formula will become – left right data
which is the formula for the postorder traversal.
function postOrder(root) {
let ans = [];
if (root === null) return ans;
// push root into stack
let stack = [root];
// loop while stack is not empty
while (stack.length) {
let cur = stack.pop();
// push the node data to ans
ans.push(cur.data);
// push left node into stack
if (cur.left) {
stack.push(cur.left);
}
// push right node into stack
if (cur.right) {
stack.push(cur.right);
}
}
return ans.reverse();
}
Time Complexity: O(n) (each tree node is processed once)
Space Complexity: O(h) + O(n) ~= O(n)
h is the height. of the tree.
Conclusion
We have seen the implementation of the binary tree in javascript and its traversal preorder, inorder, and postorder in both recursive and non-recursive ways.
The idea of this article is to give you consolidated knowledge all at once. From the interview point of view, the non-recursive traversals are very important.
Read my other articles –
I’m also on medium, please follow me there!
Thanks for reading the article!
