Simple 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.

recursive tree traversal
Credit – https://leetcode.com/andvary/

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

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

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

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.


Posted

in

by

Tags:

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *