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:-

- Preorder (Root, Left, Right)
- Inorder (Left, Root, Right)
- Postorder (Left, Right, Root)
- 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

`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); };

Also read, They Were Promised Coding Jobs in Appalachia. Now They Say It Was a Fraud.

## 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

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

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); };

Also read, Understanding Binary Search Trees with Js

## Final Words

I hope you like this article, please share your thoughts in the comment section and also share it more with your friends and colleagues if you like it also check out more articles on JavaScript, coding, or even technology.

## Leave a Reply