Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in JavaScript

Pre-Order Traversal

Explore how to perform pre-order traversal on binary trees, visiting nodes in root-left-right order. Understand the JavaScript implementation within a BinarySearchTree class and grasp its linear time complexity to prepare for coding interviews.

We'll cover the following...

Introduction

In pre-order traversal, the current node will be visited before its children nodes. Therefore, it is called the pre-order traversal.

The root of the tree will always be the first one to be visited.

In pre-order traversal, the elements are traversed in “root-left-right” order.

Here is a high-level description of the algorithm for Pre-Order traversal, starting from the root node:

  1. Visit the currentNode, i.e., print the value stored at the node

  2. Call the preOrderPrint() function on the left subtree of the currentNode.

  3. Call the preOrderPrint() function on the right subtree of the currentNode.

Implementation in JavaScript

Here is how we will implement the preOrderPrint in JavaScript:

Node.js
preOrderPrint(currentNode) {
  //if the currentNode IS NOT EQUAL to null
    if (currentNode!==null) {
        //print its value
        console.log(currentNode.val);
        //make recursive call to the left subtree
        this.preOrderPrint(currentNode.leftChild);
         //make recursive call to the right subtree
        this.preOrderPrint(currentNode.rightChild);
    }
  //if the currentNode IS EQUAL to null, then 
  //we simply return
}

Yes, it is as simple as that!

Putting it in the BinarySearchTree Class

Node.js
class Node {
    constructor(value) {
        this.val = value;
        this.leftChild = null;
        this.rightChild = null;
    }
}
class BinarySearchTree {
    constructor(rootValue) {
        this.root = new Node(rootValue);
    }
    insert(currentNode, newValue) {
        if (currentNode === null) {
            currentNode = new Node(newValue);
        } else if (newValue < currentNode.val) {
            currentNode.leftChild = this.insert(currentNode.leftChild, newValue);
        } else {
            currentNode.rightChild = this.insert(currentNode.rightChild, newValue);
        }
        return currentNode;
    }
    insertBST(newValue) {
        if(this.root==null){
            this.root=new Node(newValue);
            return;
        }
        this.insert(this.root, newValue);
    }
    preOrderPrint(currentNode) {
        if (currentNode!==null) {
            console.log(currentNode.val);
            this.preOrderPrint(currentNode.leftChild);
            this.preOrderPrint(currentNode.rightChild);
        }
    }
}
var BST = new BinarySearchTree(6);
console.log("The root val for BST : ", BST.root.val)
BST.insertBST(4);
BST.insertBST(9);
BST.insertBST(5);
BST.insertBST(2);
BST.insertBST(8);
BST.insertBST(12);
BST.insertBST(10);
BST.insertBST(14);
BST.preOrderPrint(BST.root);

Explanation

First, we create an object named BST of the BinarySearchTree class and insert some values into it. We will then pass BST.root(line 56) to the preOrderPrint() function.

If the node passed into the function is not null, this function prints the value at the node and calls preOrderPrint() on the left child first, i.e., the left subtree and then on the right child, i.e., the right subtree.

The recursive call to the rightChild only takes place once all the subsequent calls to the left subtree have been executed.

When the recursive calls will hit the null nodes, they will return from the function without doing anything.

If you run the code for the BST given above, it will print out the following output:

[6,4,2,5,9,8,12,10,14][6,4,2,5,9,8,12,10,14]

Time Complexity

This is a linear-time algorithm, i.e., the time complexity of preOrderPrint() is in O(n)O(n) because a total of nn recursive calls occur.

If you have understood pre-order traversal clearly, it will be a piece of cake for you to understand the rest of the traversals, as all three of them are similar to one another. You can also now check your insert function as you are able to print the tree.