BST Insert Operation in DSA Typescript - Build from Scratch

BST Insert Operation

📖 Scenario: You are building a simple phone book app that stores contacts in a Binary Search Tree (BST). Each contact has a unique phone number. You want to add new contacts in the correct position in the BST so that searching is fast.

🎯 Goal: Build a TypeScript program that creates a BST node class, sets up an initial BST, inserts a new contact with a phone number into the BST, and prints the BST in order.

📋 What You'll Learn

Create a Node class with phoneNumber, left, and right properties

Create a variable root that is the root node of the BST with phone number 50

Create a variable newPhoneNumber with the value 30

Write a function insertNode that inserts a new phone number into the BST correctly

Print the BST phone numbers in ascending order after insertion

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and databases use BSTs to store and quickly find data.

💼 Career

Understanding BST insertions is important for software engineers working with data structures and algorithms.

1

Create the BST Node class and initial root node

Create a class called Node with a constructor that takes a phoneNumber (number) and sets left and right to null. Then create a variable called root and set it to a new Node with phoneNumber 50.

DSA Typescript

# Your code here

Hint

Define a class with a constructor and create the root node with phone number 50.

2

Create the new phone number variable

Create a variable called newPhoneNumber and set it to the number 30.

DSA Typescript

class Node {
    phoneNumber: number;
    left: Node | null;
    right: Node | null;

    constructor(phoneNumber: number) {
        this.phoneNumber = phoneNumber;
        this.left = null;
        this.right = null;
    }
}

const root = new Node(50);

# Your code here

Hint

Just create a variable with the exact name and value.

3

Write the insertNode function

Write a function called insertNode that takes two parameters: root (Node) and phoneNumber (number). It inserts a new node with phoneNumber into the BST rooted at root following BST rules. Return the root node after insertion.

DSA Typescript

class Node {
    phoneNumber: number;
    left: Node | null;
    right: Node | null;

    constructor(phoneNumber: number) {
        this.phoneNumber = phoneNumber;
        this.left = null;
        this.right = null;
    }
}

const root = new Node(50);

const newPhoneNumber = 30;

# Your code here

Hint

Use recursion to insert the new phone number in the correct place.

4

Insert the new phone number and print the BST in order

Call insertNode with root and newPhoneNumber and store the result back in root. Then write a function called inOrderPrint that prints all phone numbers in the BST in ascending order separated by spaces. Finally, call inOrderPrint(root).

DSA Typescript

class Node {
    phoneNumber: number;
    left: Node | null;
    right: Node | null;

    constructor(phoneNumber: number) {
        this.phoneNumber = phoneNumber;
        this.left = null;
        this.right = null;
    }
}

const root = new Node(50);

const newPhoneNumber = 30;

function insertNode(root: Node | null, phoneNumber: number): Node {
    if (root === null) {
        return new Node(phoneNumber);
    }
    if (phoneNumber  root.phoneNumber) {
        root.right = insertNode(root.right, phoneNumber);
    }
    return root;
}

# Your code here

Hint

Insert the new phone number and print the BST in order to see the sorted phone numbers.

Practice

1. What is the main purpose of the insert operation in a Binary Search Tree (BST)?

easy

A. To add a new node while keeping the BST property intact

B. To delete a node from the BST

C. To find the maximum value in the BST

D. To balance the BST after insertion

Solution

1. Step 1: Understand BST property

   A BST keeps nodes ordered so that left child is smaller and right child is larger than the parent.

2. Step 2: Purpose of insert operation

   Insert adds a new node in the correct position to maintain this order.

3. Final Answer:

   To add a new node while keeping the BST property intact -> Option A

4. Quick Check:

   Insert = Add node maintaining order [OK]

Hint: Insert adds nodes without breaking BST order [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Assuming insert finds max or min values

2. Which of the following is the correct TypeScript function signature for inserting a value into a BST node?

easy

A. function insert(root: Node, value: number): void

B. function insert(value: number, root: Node): void

C. function insert(root: Node | null, value: number): Node | null

D. function insert(root: Node, value: string): Node

Solution

1. Step 1: Analyze parameter types

   Insert needs the root node (which can be null if tree is empty) and the value to insert (a number).

2. Step 2: Analyze return type

   It returns the updated root node (Node or null if empty).

3. Final Answer:

   function insert(root: Node | null, value: number): Node | null -> Option C

4. Quick Check:

   Correct params and return type [OK]

Hint: Insert returns updated root, accepts root or null [OK]

Common Mistakes:

• Swapping parameter order
• Using void return type instead of returning Node
• Using wrong value type like string

3. Given the following BST and the insert operation call insert(root, 7), what will be the in-order traversal of the BST after insertion?

Initial BST in-order: 3 -> 5 -> 8 -> 10

Code snippet:

class Node {
  constructor(public val: number, public left: Node | null = null, public right: Node | null = null) {}
}

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

medium

A. [3, 5, 8, 7, 10]

B. [3, 5, 8, 10, 7]

C. [7, 3, 5, 8, 10]

D. [3, 5, 7, 8, 10]

Solution

1. Step 1: Locate insertion point for 7

   7 is greater than 5 but less than 8, so it goes to the left of 8.

2. Step 2: Perform in-order traversal after insertion

   In-order visits left, root, right: 3, 5, 7, 8, 10.

3. Final Answer:

   [3, 5, 7, 8, 10] -> Option D

4. Quick Check:

   In-order sorted after insert [OK]

Hint: Insert left if smaller, right if larger [OK]

Common Mistakes:

• Placing 7 incorrectly after 8
• Confusing in-order traversal order
• Ignoring recursive insert logic

4. The following TypeScript code attempts to insert a value into a BST but has a bug. What is the error?

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

medium

A. The base case is missing

B. The recursive calls do not update root.left or root.right

C. The function returns void instead of Node

D. The comparison operator should be < instead of <=

Solution

1. Step 1: Check recursive calls

   The calls to insert do not assign the result back to root.left or root.right, so tree structure is not updated.

2. Step 2: Correct recursive assignment

   Should be root.left = insert(root.left, val) or root.right = insert(root.right, val) to update links.

3. Final Answer:

   The recursive calls do not update root.left or root.right -> Option B

4. Quick Check:

   Must assign recursive insert result to child [OK]

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

Common Mistakes:

• Forgetting to assign recursive call result
• Misunderstanding base case presence
• Changing comparison operator unnecessarily

5. You have a BST with nodes 10, 5, 15, 3, 7, 12, 18. You want to insert 6. Which sequence of nodes will you visit during the insert operation?

hard

A. [10, 5, 7]

B. [10, 15, 12]

C. [10, 5, 3]

D. [10, 15, 18]

Solution

1. Step 1: Start at root 10

   6 is less than 10, so move to left child 5.

2. Step 2: Compare with 5 and 7

   6 is greater than 5, move to right child 7. 6 is less than 7, so insert here.

3. Final Answer:

   [10, 5, 7] -> Option A

4. Quick Check:

   Traverse nodes comparing 6 until insertion point [OK]

Hint: Follow left/right based on comparison until null [OK]

Common Mistakes:

• Visiting wrong subtree based on comparison
• Skipping nodes in path
• Confusing insertion path with traversal order