BST Insert Operation in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting nodes in BST

What is the printed state of the BST after inserting the values 10, 5, 15, 3, 7 in that order? The BST is printed using in-order traversal (left -> root -> right).

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(value: number) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  inOrder(node: Node | null, result: number[] = []) {
    if (!node) return result;
    this.inOrder(node.left, result);
    result.push(node.value);
    this.inOrder(node.right, result);
    return result;
  }
}

const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
console.log(bst.inOrder(bst.root));

A [10, 5, 15, 3, 7]

B [3, 5, 7, 10, 15]

C [15, 10, 7, 5, 3]

D [3, 7, 5, 10, 15]

💡 Hint

Remember that in-order traversal of a BST prints values in sorted order.

In-order traversal visits left subtree, then root, then right subtree. After inserting 10, 5, 15, 3, 7, the BST in-order traversal outputs sorted values: 3, 5, 7, 10, 15.

❓ Predict Output

intermediate

BST structure after inserting duplicate value

What is the in-order traversal output after inserting values 20, 10, 30, 20 into an empty BST? Assume duplicates are inserted to the right subtree.

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(value: number) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  inOrder(node: Node | null, result: number[] = []) {
    if (!node) return result;
    this.inOrder(node.left, result);
    result.push(node.value);
    this.inOrder(node.right, result);
    return result;
  }
}

const bst = new BST();
bst.insert(20);
bst.insert(10);
bst.insert(30);
bst.insert(20);
console.log(bst.inOrder(bst.root));

A [10, 20, 20, 30]

B [10, 20, 30]

C [20, 10, 20, 30]

D [10, 30, 20, 20]

💡 Hint

Duplicates go to the right subtree, so the second 20 is placed as right child of the first 20.

Inserting duplicate 20 goes to the right subtree of the first 20. In-order traversal visits left, root, right, so output is [10, 20, 20, 30].

🔧 Debug

advanced

Identify the bug in BST insert method

What error will occur when running this BST insert code if we try to insert 5 into the BST with root 10 and left child 5?

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(value: number) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else if (value > current.value) {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }
}

const bst = new BST();
bst.root = new Node(10);
bst.root.left = new Node(5);
bst.insert(5);

A No error, insertion succeeds

B TypeError: Cannot read property 'left' of null

C SyntaxError: Unexpected token 'else if'

D Infinite loop causing program to hang

💡 Hint

Check what happens when value equals current.value in the loop.

The insert method does not handle the case when value equals current.value, so the loop never breaks or inserts, causing infinite loop.

❓ Predict Output

advanced

BST structure after multiple inserts and in-order traversal

After inserting the values 50, 30, 70, 20, 40, 60, 80 into an empty BST, what is the in-order traversal output?

DSA Typescript

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

class BST {
  root: Node | null = null;

  insert(value: number) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  inOrder(node: Node | null, result: number[] = []) {
    if (!node) return result;
    this.inOrder(node.left, result);
    result.push(node.value);
    this.inOrder(node.right, result);
    return result;
  }
}

const bst = new BST();
[50, 30, 70, 20, 40, 60, 80].forEach(v => bst.insert(v));
console.log(bst.inOrder(bst.root));

A [80, 70, 60, 50, 40, 30, 20]

B [50, 30, 20, 40, 70, 60, 80]

C [20, 30, 40, 50, 60, 70, 80]

D [20, 40, 30, 60, 80, 70, 50]

💡 Hint

In-order traversal prints BST values in ascending order.

The in-order traversal visits nodes in ascending order: 20, 30, 40, 50, 60, 70, 80.

🧠 Conceptual

expert

Number of nodes in BST after insertions

If you insert the values [15, 10, 20, 10, 25, 15] into an empty BST where duplicates are inserted to the right subtree, how many nodes will the BST contain?

A 6

B 4

C 3

D 5

💡 Hint

Count each inserted value as a node, including duplicates inserted to the right.

All 6 values are inserted, but duplicates 10 and 15 are inserted as new nodes to the right subtree, so total nodes = 6.