Tree Traversals in JavaScript

A tree is a non-linear hierarchical data structure and it is a combination of both nodes and edges. Nodes in the tree store the values and these nodes are connected to each other with Edges. The topmost node of the tree doesn't have any Parent node and is called a Root node.

The below Binary search tree is labeled with important terms.


Fundamental Terms

  • Node ? Has a pointer to another node and the ability to store a value of any data type.

  • Root ? This node is at the very top of the tree and is parentless.

  • Child ? Child nodes are the nodes that are immediately connected to their corresponding parent node.

  • Edge ? The edge of the tree is the link that connects two nodes.

  • Path ? The order of nodes along a tree's edges is referred to as its path.

  • Parent ? Parent node has child nodes attached as subtrees.

  • Leaf ? The node which is not having any child node attached to it.

  • Subtree ? It is a smaller part of a tree, considering an internal node as its root and all the paths connected to it as child nodes.

  • Traversing ? It walks through each node in a tree in a particular order.

  • Levels ? The number of descendants from a node to its root node is known as a level.

  • Height of the tree ? Path from root to leaf. It is defined as the maximum height of the subtree + 1.

Tree traversal Data Structures

In general, the word traverse means "travel through (or, across)". The tree traversals are the operations where we visit each and every node of a tree.

There are various types of traversal techniques in a tree ?

  • In-order Traversal ? The traversal of the tree recursively by visiting the left subtree, root node and then the right subtree (in BST) is called in-order traversal. This traversal is also called symmetric traversal.

    left ? root ? right

  • Pre-order Traversal ? In this traversal ? The process of traversing the root node first then left and right recursively in a tree. Prefix traversal is the term also used to describe this process

    root ? left ? right

  • Post?order Traversal ? The process of traversing the left node, right node and then root node recursively in a tree. Postfix traversal is another name for this traversal.

    left ?right ? root

We always start from the root (head) node since all nodes are connected by edges (links). In other circumstances, we are unable to access a tree node at random.

Implementation of BST traversals

In this below script we have implemented all three traversals in uniquely.

Example


<! DOCTYPE html>
<html>
   <head>
      <script>
         class Node {
            constructor(value) {
               this.value = value;
               this.left = null;
               this.right = null;
            }
         }
         class BinarySearchTree {
            constructor() {
               this.root = null;
            }

            inserting(value) {
               let node = new Node(value);
               if(this.root == null) {
                  this.root = node;
               }else {
                  this.insertNode(this.root, node);
               }
            }

            insertNode(root, newNode) {
               if(newNode.value < root.value) {
                  if(root.left == null) {
                     root.left = newNode;
                  } else {
                     this.insertNode(root.left, newNode);
                  }
               } else if(newNode.value > root.value) {
                  if(root.right == null) {
                     root.right = newNode;
                  } else {
                     this.insertNode(root.right, newNode);
                  }
               }
            }
            getRootNode() {
               return this.root;
            }

            /* implementation of individual operations of traversal in tree */

            preorderTrav(root) {
               if(root != null) {
                  document.write(root.value); // Traverse the root node
                  this.preorderTrav(root.left); /* Traverse the left subtree */
                  this.preorderTrav(root.right); /* Traverse the right subtree */
               }
            }

            inorderTrav(root) {
               if(root != null) {
                  this.inorderTrav(root.left); /* Traverse the left subtree */
                  document.write(root.value); // Traverse the root node
                  this.inorderTrav(root.right); /* Traverse the right subtree */
               }
            }

            postorderTrav(root) {
               if(root != null) {
                  this.postorderTrav(root.left); /* Traverse the left subtree */
                  this.postorderTrav(root.right); /* Traverse the right subtree */
                  document.write(root.value); // Traverse the root node
               }
            }
         }
         
         var bst = new BinarySearchTree();
         bst.inserting(30);
         bst.inserting(50);
         bst.inserting(20);
         bst.inserting(14);
         bst.inserting(44);
         bst.inserting(34);
         bst.inserting(26);
         bst.inserting(10);
         bst.inserting(19);
         bst.inserting(54);
         
         var root = bst.getRootNode();
         document.write("preorder traversal of the binary tree is <br>");
         bst.preorderTrav(root);
         document.write('<br>');
         document.write('inorder traversal of the binary tree is <br>');
         bst.inorderTrav(root);
         document.write('<br>');
         document.write('Postorder traversal of the binary tree is <br>');
         bst.postorderTrav(root);
         document.write('<br>');
      </script>
   </head>
   <body>
   </body>
</html>

Output

The output of the above script will be ?

Pre-order traversal of the binary tree is
30 20 14 10 19 26 50 44 34 54

In-order traversal of the binary tree is
10 14 19 20 26 30 34 44 50 54

Post-order traversal of the binary tree is
10 19 14 26 20 34 44 54 50 30
Updated on: 2022-11-18T05:56:44+05:30

3K+ Views

Kickstart Your Career

Get certified by completing the course

Get Started
Advertisements