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.