Tree traversal in Javascript

Learn how to perform tree traversal in javascript.

Unlike linear data structures such as Array, Linked list, Doubly linked list which can be traversed in only single direction i.e either forward or backward.

Trees can be traversed in different ways by visiting sibling nodes.

There are two types of traversing for tree.

• BFS (Breadth First Search).
• DFS (Depth First search).

Breadth first traversing of tree

In BFS we start from the top level(any given node) and explores all the sibling nodes before moving to the next level in the tree. Using BFS we perform

• Level order traversal.

---

Depth first traversing of tree

In DFS we move to the depth that is to the lowest level node first then do backtracking to the neighboring nodes. Following traversal are example of DFS.

• In Order traversal.
• Pre Order traversal.
• Post Order traversal.

---

Level order traversal.

It is a variant of BFS and in this we visit all the nodes starting from the top.

To get the values of each node of the tree, we will use the following approach.

• Get the height of the tree first.
• Then print all the nodes at the each level.

//Get height of the tree
const treeHeight = (node) => {
  //If null return 0
  if(node === null){
    return 0;
  }
  
  //Get left sub tree height
  const leftHeight = treeHeight(node.left);
  
  //Get right sub tree height
  const rightHeight = treeHeight(node.right);
  
  //Return the max of them
  return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

//Print all the nodes
const printNode = (node, level) => {
  //If null return
  if(node === null){
    return;
  }
  
  //If at node print the data
  if(level === 1){
    console.log(node.key)
  }
  
  //Else recursively print all the nodes at each level
  if(level > 1){
    printNode(node.left, level - 1)
    printNode(node.right, level - 1);
  };
}

const levelOrderTraversal = (node) => {
  const height = treeHeight(node);
  
  //Print node at each level
  for(let i = 1; i <= height; i++)  
  { 
    printNode(node, i); 
  } 
}

Input:
const tree = new BinarySearchTree();
tree.insert(11);
tree.insert(9);
tree.insert(15);
tree.insert(8);
tree.insert(10);
tree.insert(12);
tree.insert(16);

const root = tree.getRoot();
levelOrderTraversal(root);

Output:
11
9
15
8
10
12
16

Time complextiy: O(n).
Space complexity: O(n).

---

In Order Traversal

With in order traversal we can print the elements of the tree in ascending order.

Implementation

• If node is not null.
• Traverse the left subtree.
• Print the node.
• Traverse the right subtree.

const InOrderTraverse = (node) => {
   if (node !== null) {
     //Traverse the left subtree
     InOrderTraverse(node.left);
     
     //Print the node
     console.log(node.key);
     
     //Traverse the right subtree
     InOrderTraverse(node.right);
   }
  };

Input:
const tree = new BinarySearchTree();
tree.insert(11);
tree.insert(9);
tree.insert(15);
tree.insert(8);
tree.insert(10);
tree.insert(12);
tree.insert(16);

const root = tree.getRoot();
InOrderTraverse(root);

Output:
8
9
10
11
12
15
16

Time complextiy: O(n).
Space complexity: O(n).

---

Pre order traversal

Pre order traversal is used to create a copy of tree because it visits nodes in the same order as they were added. Also it can be used to prefix expression of a expression tree.

Implementation

• If node is not null.
• Print the node.
• Traverse all the left sub tree.
• Then traverse all the right sub tree

const PreOrderTraverse = (node) => {
   if (node !== null) {
     //Print the node
     console.log(node.key);
     
     //Traverse the left subtree
     PreOrderTraverse(node.left);
     
     //Traverse the right subtree
     PreOrderTraverse(node.right);
   }
};

Input:
const tree = new BinarySearchTree();
tree.insert(11);
tree.insert(9);
tree.insert(15);
tree.insert(8);
tree.insert(10);
tree.insert(12);
tree.insert(16);

const root = tree.getRoot();
PreOrderTraverse(root);

Output:
11
9
8
10
15
12
16

Time complextiy: O(n).
Space complexity: O(n).

---

Post Order Traversal

Porst Order Traversal is used for deleting tree. Because before deleting any parent node we want to delete all the child and then remove parents. Post order traversal visits the node in same way.

Implementation

• If node is not null.
• Traverse the left subtree.
• Traverse the right subtree.
• Print the node.

const PostOrderTraverse = (node) => {
   if (node !== null) {
     //Traverse the left subtree
     PostOrderTraverse(node.left);
     
     //Traverse the right subtree
     PostOrderTraverse(node.right);
     
     //Print the node
     console.log(node.key);
   }
};

Input:
const tree = new BinarySearchTree();
tree.insert(11);
tree.insert(9);
tree.insert(15);
tree.insert(8);
tree.insert(10);
tree.insert(12);
tree.insert(16);

const root = tree.getRoot();
PostOrderTraverse(root);

Output:
8
10
9
12
16
15
11

Time complextiy: O(n).
Space complexity: O(n).