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

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

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

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

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.