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.

Practice

1. What does the insert operation do in a Binary Search Tree (BST)?

easy

A. Searches for a node with a given value

B. Adds a new node in the correct position to maintain BST order

C. Deletes a node from the tree

D. Balances the tree automatically after insertion

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes are smaller and right child nodes are larger than the parent node.

2. Step 2: Purpose of insert operation

   The insert operation places a new value in the tree so that this property remains true.

3. Final Answer:

   Adds a new node in the correct position to maintain BST order -> Option B

4. Quick Check:

   Insert means add node correctly [OK]

Hint: Insert means add node keeping BST order intact [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Assuming insert searches only without adding

2. Which of the following is the correct syntax to insert a value val into a BST node root in JavaScript?

easy

A. root = insert(root, val);

B. root.insert(val);

C. insert(root, val);

D. insert(val, root);

Solution

1. Step 1: Understand function usage in BST insert

   Insert usually returns the new root after insertion, so assignment is needed.

2. Step 2: Check parameter order and assignment

   The function takes the root and value, returns updated root, so root = insert(root, val); is correct.

3. Final Answer:

   root = insert(root, val); -> Option A

4. Quick Check:

   Assign updated root after insert [OK]

Hint: Insert returns new root, so assign it back [OK]

Common Mistakes:

• Calling insert without assignment
• Passing parameters in wrong order
• Using method call on root without method defined

3. What will be the inorder traversal output after inserting 5 into this BST?

    10
   /  
  3    15
   
    4

Insert 5 and then print inorder traversal.

medium

A. [3, 5, 4, 10, 15]

B. [3, 4, 10, 5, 15]

C. [3, 4, 5, 10, 15]

D. [5, 3, 4, 10, 15]

Solution

1. Step 1: Insert 5 into BST

   Start at root 10, 5 < 10 go left to 3, 5 > 3 go right to 4, 5 > 4 insert as right child of 4.

2. Step 2: Perform inorder traversal

   Inorder visits left, root, right: nodes visited in order: 3, 4, 5, 10, 15.

3. Final Answer:

   [3, 4, 5, 10, 15] -> Option C

4. Quick Check:

   Inorder sorted after insert [OK]

Hint: Inorder traversal of BST is sorted list [OK]

Common Mistakes:

• Inserting 5 as left child of 4
• Mixing preorder or postorder traversal output
• Ignoring BST property during insertion

4. Given this insert function snippet, what is the error?

function insert(root, val) {
  if (root == null) {
    return new Node(val);
  }
  if (val < root.val) {
    insert(root.left, val);
  } else {
    insert(root.right, val);
  }
  return root;
}

medium

A. Returning root before insertion

B. Incorrect base case condition

C. Using '==' instead of '===' for null check

D. Missing assignment of recursive insert result to root.left or root.right

Solution

1. Step 1: Check recursive calls

   Recursive calls to insert do not assign the returned node back to root.left or root.right, so tree structure won't update.

2. Step 2: Correct recursive assignment

   Should assign: root.left = insert(root.left, val); or root.right = insert(root.right, val); to update links.

3. Final Answer:

   Missing assignment of recursive insert result to root.left or root.right -> Option D

4. Quick Check:

   Assign recursive insert result to child [OK]

Hint: Always assign recursive insert result to child pointer [OK]

Common Mistakes:

• Ignoring assignment in recursion
• Confusing base case with recursive step
• Thinking '==' causes error here

5. You have a BST with nodes 20, 10, 30. You insert 25, then 5, then 35. What is the preorder traversal of the BST after all insertions?

hard

A. [20, 10, 5, 30, 25, 35]

B. [20, 30, 25, 35, 10, 5]

C. [10, 5, 20, 30, 25, 35]

D. [20, 10, 30, 5, 25, 35]

Solution

1. Step 1: Insert nodes step-by-step

   Start with root 20, left 10, right 30.
   Insert 25: 25 < 30 and > 20, goes left of 30.
   Insert 5: less than 10, goes left of 10.
   Insert 35: greater than 30, goes right of 30.

2. Step 2: Preorder traversal

   Preorder visits root, left subtree, right subtree.
   Visit 20, then left subtree (10, 5), then right subtree (30, 25, 35).
   So preorder: [20, 10, 5, 30, 25, 35]

3. Final Answer:

   [20, 10, 5, 30, 25, 35] -> Option A

4. Quick Check:

   Preorder = root-left-right [OK]

Hint: Preorder = root, left subtree, right subtree [OK]

Common Mistakes:

• Mixing preorder with inorder or postorder
• Inserting nodes in wrong position
• Forgetting to update tree after insert