Friday, September 22, 2023
HomeData Structures and AlgorithmSimple Explanation of Tree traversal Operations with JavaScript

# Simple Explanation of Tree traversal Operations with JavaScript

Tree traversal and deletion operations are trivial and very important methods that every developer should know. Unlike Array, String, or Linked List, where traversing through each element is simple and logical way due to the linear structure in trees, traversing through each element is a little different due to its non-linear structure.

In this blog, we will understand different method traversing methods we can employ and how we can use the same traversing method to reach a particular element and delete it from the tree.

# Types of Tree Traversal Method in Trees

There are a total of 4 different ways we can employ to traverse through each node of the tree:-

1. Preorder (Root, Left, Right)
2. Inorder (Left, Root, Right)
3. Postorder (Left, Right, Root)
4. Breadth-First or Level Order Traversal

Note:- We will discuss Breadth-First or Level Order Traversal method in upcoming graph blogs.

## Preorder (Root, Left, Right)

In the Preorder Traversal method, we traverse from the root to the left subtree and then the right subtree. The following steps are required to follow in the Preorder Traversal method,

• Visit Root node
• Traverse or visit all the nodes on the left side of the tree
• Traverse or visit all the nodes on the right side of the tree

### Implementation of Preorder Traversal method using JS

#### Iterative Method

The goal is to maintain a stack of nodes to visit as we traverse down the tree. As we traverse down, We first push the root value inside the stack and then we save it inside the `output` array. Then we check if the current node right is not null then we push it inside the stack and then we check if the node left is not null then we push also push it in the stack.
Â
```var preorderTraversal = function (root) {
let output = [];

if (!root) {
return output;
}

let stack = [];

stack.push(root);

while (stack.length != 0) {
let curr = stack.pop();
output.push(curr.val);

if (curr.right != null) {
stack.push(curr.right);
}

if (curr.left != null) {
stack.push(curr.left);
}
}

return output;
};```
Â

Time Complexity – O(n)

Space Complexity – O(h)

#### Recursive Method

• Visit the current node
• Recursively traverse through the left subtree
• Recursively traverse through the right subtree.
```var preorderTraversal = function (root) {
let result = [];
// Recursive function to traverse through subtrees
preorder(root, result);
return result;
};
const preorder = (node, result) => {
if (!node) return null;
// Visit node
result.push(node.val);
// Traverse through left subtree
preorder(node.left, result);
// Traverse through right subtree
preorder(node.right, result);
};```

## Inorder (Left, Root, Right)

In the Inorder Traversal method, we traverse from the left subtree to the root and then the right subtree. This method is also used to visit the nodes in ascending order. Following steps are required to follow in the Inorder Traversal method,

• Traverse or visit all the nodes on the left side of the tree
• Visit Root node
• Traverse or visit all the nodes on the right side of the tree

### Implementation of the Inorder Traversal method using JS

#### Iterative Method

The goal is to maintain a stack of nodes to visit as we traverse down the tree. As we traverse down, We go left and push all the left nodes first in the stack. Once we reach the bottom, we store the node value and traverse right.
```var inorderTraversal = function(root) {
const output = [];

if (root === null) {
return output;
}
const stack = [];
let curr = root;

while (curr !== null || stack.length !== 0) {
if (curr !== null) {
stack.push(curr);
curr = curr.left;
} else {
curr = stack.pop();
output.push(curr.val);
curr = curr.right;
}
}

return output;
};```

Time Complexity – O(n)

Space Complexity – O(h) ** h -> height of the tree

#### Recursive Method

• Recursively traverse through the left subtree
• Visit the current node
• Recursively traverse through the right subtree.
```var inorderTraversal = function (root) {
// Initialize array of values
let result = [];

// Recursive function to traverse through subtrees
inorder(root, result);

return result;
};

const inorder = (node, result) => {
if (!node) return null;
// Traverse through left subtree
inorder(node.left, result);
// Visit node
result.push(node.val);
// Traverse through right subtree
inorder(node.right, result);
};```
Â

Also read, Introduction to Tree Data Structure

## Postorder (Left, Right, Root)

In the Postorder Traversal method, we traverse from the right subtree to the left subtree and then finally to the root node. The following steps are required to follow in the Preorder Traversal method,

• Traverse or visit all the nodes on the left side of the tree
• Traverse or visit all the nodes on the right side of the tree
• Visit Root node

### Implementation of Postorder Traversal method using JS

#### Iterative Method

The goal is to maintain a stack of nodes to visit as we traverse down the tree. As we traverse down, we check if the current node is not null then we push all the left nodes first in the stack, Once we reach the bottom, we store the node value and traverse right.
```var postorderTraversal = function (root) {
let stack = [];
let output = [];
let curr = root;

while (curr != null || stack.length != 0) {
if (curr != null) {
stack.push(curr);
curr = curr.left;
} else {
let temp = stack[stack.length - 1].right;
if (temp == null) {
temp = stack.pop();
output.push(temp.val);
while (stack.length != 0 && temp == stack[stack.length - 1].right) {
temp = stack.pop();
output.push(temp.val);
}
} else {
curr = temp;
}
}
}

return output;
};```
Â

Time Complexity – O(n^2)

Space Complexity – O(h)

#### Recursive Method

• Recursively traverse through the left subtree
• Recursively traverse through the right subtree.
• Visit the current node
```var postorderTraversal = function (root) {
// Initialize array of values
let result = [];

// Recursive function to traverse through subtrees
postorder(root, result);

return result;
};

const postorder = (node, result) => {
if (!node) return null;
// Traverse through left subtree
postorder(node.left, result);
// Traverse through right subtree
postorder(node.right, result);
// Visit node
result.push(node.val);
};```

## Final Words

Aaquib Ahmedhttps://aaquib.netlify.app
Hi, I'm Aaquib Ahmed, a passionate self-taught frontEnd web developer based in Bangalore, India. I tend to make use of modern web technologies to build websites that look great, feels fantastic, and functions correctly. I am especially focusing on Reactjs.
RELATED ARTICLES