BST Property and Why It Matters in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inserting Nodes in BST

What is the printed state of the BST after inserting the values 10, 5, 15, 3, 7 in that order?

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;
      }
    }
  }

  printInOrder(node: Node | null = this.root): string {
    if (!node) return '';
    const left = this.printInOrder(node.left);
    const right = this.printInOrder(node.right);
    return (left ? left + ' -> ' : '') + node.value + (right ? ' -> ' + right : '');
  }
}

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

A 3 -> 5 -> 7 -> 10 -> 15

B 10 -> 5 -> 3 -> 7 -> 15

C 15 -> 10 -> 7 -> 5 -> 3

D 5 -> 3 -> 7 -> 10 -> 15

💡 Hint

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

In a BST, the in-order traversal visits nodes in ascending order. After inserting 10, 5, 15, 3, and 7, the tree structure ensures the in-order print is sorted: 3 -> 5 -> 7 -> 10 -> 15.

🧠 Conceptual

intermediate

Why BST Property Matters for Search Efficiency

Why does the BST property help in searching for a value efficiently compared to a simple binary tree?

A Because it stores values in a linked list fashion, making traversal faster.

B Because it keeps the tree balanced automatically, ensuring minimal height.

C Because it allows deciding to go left or right at each node based on value comparison, reducing search space.

D Because it duplicates values to speed up search operations.

💡 Hint

Think about how the BST property guides the search path.

The BST property means left children are smaller and right children are larger than the node. This lets us decide which subtree to search next, cutting the search space roughly in half each step, making search efficient.

🔧 Debug

advanced

Identify the Bug in BST Insert Method

What error will occur when running this insert method in a BST if the BST property is violated by inserting duplicates incorrectly?

DSA Typescript

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;
    }
  }
}

A Infinite loop if inserting duplicate values

B SyntaxError due to missing return statement

C TypeError because newNode is undefined

D No error, duplicates are handled correctly

💡 Hint

Check what happens when value equals current.value.

Using <= for deciding to go left causes duplicates to always go left. If duplicates already exist on the left, the loop never ends, causing an infinite loop.

❓ Predict Output

advanced

Output After Deleting a Node with Two Children

Given a BST with nodes 20, 10, 30, 5, 15, 25, 35, what is the in-order traversal after deleting node 20?

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;
      }
    }
  }

  findMin(node: Node): Node {
    while (node.left) {
      node = node.left;
    }
    return node;
  }

  delete(value: number, node: Node | null = this.root): Node | null {
    if (!node) return null;
    if (value < node.value) {
      node.left = this.delete(value, node.left);
    } else if (value > node.value) {
      node.right = this.delete(value, node.right);
    } else {
      if (!node.left) return node.right;
      if (!node.right) return node.left;
      const minRight = this.findMin(node.right);
      node.value = minRight.value;
      node.right = this.delete(minRight.value, node.right);
    }
    return node;
  }

  printInOrder(node: Node | null = this.root): string {
    if (!node) return '';
    const left = this.printInOrder(node.left);
    const right = this.printInOrder(node.right);
    return (left ? left + ' -> ' : '') + node.value + (right ? ' -> ' + right : '');
  }
}

const bst = new BST();
[20, 10, 30, 5, 15, 25, 35].forEach(v => bst.insert(v));
bst.delete(20);
console.log(bst.printInOrder());

A 5 -> 10 -> 15 -> 20 -> 25 -> 30 -> 35

B 5 -> 10 -> 15 -> 25 -> 30 -> 35

C 5 -> 10 -> 15 -> 25 -> 20 -> 30 -> 35

D 10 -> 15 -> 25 -> 30 -> 35

💡 Hint

Deleting a node with two children replaces it with the smallest node in the right subtree.

When deleting node 20 (root), it is replaced by the minimum node in its right subtree, which is 25. Then 25 is removed from its original position. The in-order traversal reflects this updated tree.

🧠 Conceptual

expert

Why Maintaining BST Property is Crucial for Tree Operations

Which of the following best explains why maintaining the BST property is essential for operations like search, insert, and delete to work correctly?

A Because it guarantees the tree is always perfectly balanced, minimizing height.

B Because it converts the tree into a linked list, simplifying traversal.

C Because it allows storing duplicate values in both subtrees for faster access.

D Because it ensures that the left subtree contains only smaller values and the right subtree only larger values, enabling binary search logic.

💡 Hint

Think about how the BST property guides decision making at each node.

The BST property ensures that for any node, all values in the left subtree are smaller and all in the right subtree are larger. This ordering is what allows efficient binary search-like operations on the tree.