BST Insert Operation in DSA Javascript - Build from Scratch

BST Insert Operation

📖 Scenario: You are building a simple phone book app that stores phone numbers in a Binary Search Tree (BST) to keep them sorted for quick search and insertion.

🎯 Goal: Build a BST by inserting phone numbers one by one and then print the tree in-order to see the sorted phone numbers.

📋 What You'll Learn

Create a BST node class with value, left, and right properties

Create a BST class with an insert method to add new numbers

Insert given phone numbers into the BST

Print the BST values in sorted order using in-order traversal

💡 Why This Matters

🌍 Real World

BSTs are used in phone books, contact lists, and databases to keep data sorted and allow fast insertion and search.

💼 Career

Understanding BST insertions is important for software engineers working on data storage, search engines, and performance optimization.

1

Create BST Node Class

Create a class called Node with a constructor that takes a parameter value. Inside the constructor, set this.value to value, and initialize this.left and this.right to null.

DSA Javascript

# Your code here

Hint

Think of each node as a box holding a number and links to left and right child nodes.

2

Create BST Class with Insert Method

Create a class called BST with a constructor that initializes this.root to null. Then add an insert method that takes a parameter value. Inside insert, if this.root is null, set it to a new Node with value. Otherwise, call a helper method insertNode with this.root and value.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

# Your code here

Hint

The BST starts empty. The first inserted number becomes the root.

3

Implement Insert Logic in insertNode Method

Complete the insertNode method inside the BST class. It takes parameters node and value. If value is less than node.value, check if node.left is null. If yes, set node.left to a new Node with value. Otherwise, recursively call insertNode with node.left and value. If value is greater or equal to node.value, do the same logic for the right child.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() {
        this.root = null;
    }

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

    // Complete insertNode method below
    insertNode(node, value) {
        // Your code here
    }
}

Hint

Compare the new value with current node's value to decide left or right subtree.

4

Print BST In-Order Traversal

Add a method called inOrder in the BST class that takes a parameter node. If node is not null, recursively call inOrder on node.left, then print node.value using console.log(node.value), then recursively call inOrder on node.right. Then create a BST instance, insert these phone numbers in this order: 50, 30, 70, 20, 40, 60, 80. Finally, call inOrder with the root node to print the sorted phone numbers.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() {
        this.root = null;
    }

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

    insertNode(node, value) {
        if (value < node.value) {
            if (node.left === null) {
                node.left = new Node(value);
            } else {
                this.insertNode(node.left, value);
            }
        } else {
            if (node.right === null) {
                node.right = new Node(value);
            } else {
                this.insertNode(node.right, value);
            }
        }
    }

    // Add inOrder method and insert calls below
    
    // Your code here
}

Hint

In-order traversal prints values in ascending order for BST.