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.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. Left child nodes have smaller values, right child nodes have larger values

B. All nodes have exactly two children

C. Nodes are arranged in a circular linked list

D. Each node stores the sum of its children

Solution

1. Step 1: Understand BST node arrangement

   In a BST, every node's left child has a smaller value and the right child has a larger value.

2. Step 2: Compare with other options

   Other options describe different data structures or incorrect properties.

3. Final Answer:

   Left child nodes have smaller values, right child nodes have larger values -> Option A

4. Quick Check:

   BST property = Left smaller, right larger [OK]

Hint: Remember BST orders left < node < right [OK]

Common Mistakes:

• Thinking all nodes must have two children
• Confusing BST with binary tree
• Assuming nodes store sums

2. Which TypeScript interface correctly represents a BST node?

easy

A. interface Node { value: number; parent: Node; }

B. interface Node { value: number; left: Node | null; right: Node | null; }

C. interface Node { value: number; children: Node[]; }

D. interface Node { value: number; next: Node | null; prev: Node | null; }

Solution

1. Step 1: Identify BST node structure

   A BST node has a value and two pointers: left and right, which can be null.

2. Step 2: Check options

   interface Node { value: number; left: Node | null; right: Node | null; } matches this structure; others describe linked lists or generic trees.

3. Final Answer:

   interface Node { value: number; left: Node | null; right: Node | null; } -> Option B

4. Quick Check:

   BST node = value + left + right [OK]

Hint: BST nodes have left and right, not next/prev [OK]

Common Mistakes:

• Using next/prev like linked lists
• Using children array for BST
• Missing null for leaf nodes

3. What will be the in-order traversal output of this BST?

const root = {
  value: 10,
  left: { value: 5, left: null, right: null },
  right: { value: 15, left: null, right: null }
};
function inorder(node) {
  if (!node) return [];
  return [...inorder(node.left), node.value, ...inorder(node.right)];
}
console.log(inorder(root));

medium

A. [10, 5, 15]

B. [5, 15, 10]

C. [15, 10, 5]

D. [5, 10, 15]

Solution

1. Step 1: Understand in-order traversal

   In-order visits left subtree, then node, then right subtree.

2. Step 2: Apply traversal to given tree

   Left subtree: 5, root: 10, right subtree: 15, so output is [5, 10, 15].

3. Final Answer:

   [5, 10, 15] -> Option D

4. Quick Check:

   In-order = left, root, right = [5,10,15] [OK]

Hint: In-order traversal of BST gives sorted values [OK]

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Mixing left and right subtree order
• Forgetting to return empty array for null

4. Identify the bug in this BST insertion function:

function insert(node, value) {
  if (!node) return { value, left: null, right: null };
  if (value < node.value) insert(node.left, value);
  else insert(node.right, value);
  return node;
}

medium

A. Node should have a parent pointer

B. Should compare value > node.value instead of <

C. Missing return when recursively inserting left or right

D. Function should not return anything

Solution

1. Step 1: Analyze recursive calls

   The recursive calls to insert do not assign their results back to node.left or node.right.

2. Step 2: Fix missing assignment

   We must assign: node.left = insert(node.left, value) or node.right = insert(node.right, value) to update the tree.

3. Final Answer:

   Missing return when recursively inserting left or right -> Option C

4. Quick Check:

   Recursive insert must update child pointers [OK]

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

Common Mistakes:

• Not assigning recursive call result
• Wrong comparison operator
• Expecting parent pointer in BST node

5. Given a BST, why is maintaining the BST property important when deleting a node?

hard

A. To ensure in-order traversal still returns sorted values

B. To keep the tree balanced automatically

C. To allow duplicate values in the tree

D. To convert the BST into a linked list

Solution

1. Step 1: Understand BST property role

   The BST property ensures left < node < right, which makes in-order traversal sorted.

2. Step 2: Effect of deletion on BST property

   If deletion breaks this property, in-order traversal won't be sorted, breaking BST usefulness.

3. Final Answer:

   To ensure in-order traversal still returns sorted values -> Option A

4. Quick Check:

   BST property keeps in-order sorted [OK]

Hint: BST property keeps traversal sorted after deletion [OK]

Common Mistakes:

• Thinking BST auto-balances on deletion
• Assuming duplicates are allowed by default
• Confusing BST with linked list