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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inserting Nodes in a BST

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

DSA Javascript

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

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    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, result = []) {
    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).join(' -> ') + ' -> null');

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

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

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

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

💡 Hint

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

In-order traversal visits nodes in ascending order for a BST. After inserting 10, 5, 15, 3, 7, the sorted order is 3, 5, 7, 10, 15.

🧠 Conceptual

intermediate

Why BST Property Matters for Search Efficiency

Why does the BST property (left child < parent < right child) make searching efficient compared to an unsorted binary tree?

A It balances the tree automatically, so all paths have the same length.

B It stores all values in a linked list, making search linear but simple.

C It allows skipping half of the tree at each step, reducing search time to O(log n) on average.

D It stores values randomly, so search time is unpredictable.

💡 Hint

Think about how the BST property helps decide which subtree to explore next.

The BST property lets us decide to go left or right based on comparison, effectively halving the search space each time, leading to O(log n) average search time.

🔧 Debug

advanced

Identify the Bug in BST Insertion

What error will this code cause when inserting nodes into a BST?

DSA Javascript

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

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    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;
      }
    }
  }
}

const bst = new BST();
bst.insert(10);
bst.insert(10);
console.log(bst.root.left.value);

A It prints null because the left child is never assigned.

B It throws a TypeError because left is undefined.

C It causes an infinite loop because duplicates are not handled properly.

D It prints 10 because duplicates go to the left subtree.

💡 Hint

Check how the code handles values equal to current node's value.

The code inserts duplicates to the left subtree by using <= comparison, so inserting 10 twice places the second 10 as the left child.

❓ Predict Output

advanced

Output After Deleting a Node in BST

What is the in-order traversal output after deleting node with value 5 from this BST? Inserted nodes: 10, 5, 15, 3, 7. Then delete 5.

DSA Javascript

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

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    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) {
    while (node.left) {
      node = node.left;
    }
    return node;
  }

  delete(value, node = this.root) {
    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;
      let minRight = this.findMin(node.right);
      node.value = minRight.value;
      node.right = this.delete(minRight.value, node.right);
    }
    return node;
  }

  inOrder(node, result = []) {
    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);
bst.delete(5);
console.log(bst.inOrder(bst.root).join(' -> ') + ' -> null');

A 3 -> 7 -> 10 -> 15 -> null

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

C 7 -> 10 -> 15 -> null

D 3 -> 10 -> 15 -> null

💡 Hint

When deleting a node with two children, replace it with the smallest node in the right subtree.

Deleting 5 replaces it with 7 (smallest in right subtree). The in-order traversal then is 3, 7, 10, 15.

🧠 Conceptual

expert

Effect of Violating BST Property on Search

If a binary tree does not maintain the BST property, what is the worst-case time complexity of searching for a value in it?

A O(n), because without ordering, search may need to check every node.

B O(log n), because the tree structure still halves search space.

C O(1), because any node can be found instantly.

D O(n log n), because search requires sorting first.

💡 Hint

Think about how ordering helps reduce search steps.

Without the BST property, the tree is just a binary tree with no order, so search may need to visit all nodes, leading to O(n) time.

Practice

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

easy

A. Each node has exactly two children.

B. For each node, all values in the left subtree are smaller, and all values in the right subtree are larger.

C. All nodes have the same value.

D. Nodes are arranged in a circular linked list.

Solution

1. Step 1: Understand BST node value rules

   In a BST, the left subtree contains values smaller than the node, and the right subtree contains values larger than the node.

2. Step 2: Compare options with BST definition

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. matches the BST property exactly, while others describe different structures.

3. Final Answer:

   For each node, all values in the left subtree are smaller, and all values in the right subtree are larger. -> Option B

4. Quick Check:

   BST property = left < node < right [OK]

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

Common Mistakes:

• Confusing BST with binary tree (not ordered)
• Thinking all nodes must have two children
• Assuming all values are equal

2. Which of the following is the correct way to check if a value should go to the left subtree in a BST insertion function in JavaScript?

easy

A. if (value < node.value) { insertLeft(); }

B. if (value > node.value) { insertLeft(); }

C. if (value == node.value) { insertLeft(); }

D. if (value >= node.value) { insertLeft(); }

Solution

1. Step 1: Recall BST insertion rule

   Values smaller than the current node go to the left subtree.

2. Step 2: Match condition to insertion side

   Only the condition 'value < node.value' correctly directs insertion to the left.

3. Final Answer:

   if (value < node.value) { insertLeft(); } -> Option A

4. Quick Check:

   Smaller values go left [OK]

Hint: Use < for left subtree insertion [OK]

Common Mistakes:

• Using > instead of < for left subtree
• Using == which is not for left or right
• Using >= which includes equal values incorrectly

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

    10
   /  \
  5   15
 / \    \
3   7    20

medium

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

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

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

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

Solution

1. Step 1: Understand in-order traversal

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

2. Step 2: Apply in-order to given tree

   Left subtree of 10: 3, 5, 7; then 10; then right subtree: 15, 20. Combined: [3, 5, 7, 10, 15, 20]

3. Final Answer:

   [3, 5, 7, 10, 15, 20] -> Option C

4. Quick Check:

   In-order = sorted BST values [OK]

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

Common Mistakes:

• Confusing pre-order or post-order with in-order
• Listing nodes in insertion order
• Reversing the traversal order

4. Consider this BST insertion code snippet in JavaScript:

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

What is the main issue with this code regarding BST property?

medium

A. It inserts larger values on the left subtree incorrectly.

B. It does not handle the case when node is null.

C. It returns undefined instead of the node.

D. It allows duplicate values on the left subtree, which may break strict BST rules.

Solution

1. Step 1: Analyze duplicate handling in insertion

   The condition 'value <= node.value' inserts duplicates to the left subtree.

2. Step 2: Understand BST strictness

   Strict BSTs require left subtree values strictly less than node value; duplicates on left can break this.

3. Final Answer:

   It allows duplicate values on the left subtree, which may break strict BST rules. -> Option D

4. Quick Check:

   Duplicates on left break strict BST [OK]

Hint: Use < for left to avoid duplicates on left [OK]

Common Mistakes:

• Ignoring duplicate value placement
• Thinking null check is missing
• Confusing left and right subtree insertion

5. You have a BST where some nodes violate the BST property because their left child has a value greater than the node. Which approach best fixes the tree without rebuilding it completely?

hard

A. Swap the values of the violating nodes with their children to restore BST property locally.

B. Ignore the violations as they do not affect search operations.

C. Delete all nodes and insert them again in correct order.

D. Perform an in-order traversal, collect values, then rebuild the BST from sorted values.

Solution

1. Step 1: Understand the violation type

   Left child having greater value than node breaks BST property locally.

2. Step 2: Choose minimal fix without full rebuild

   Swapping values of violating nodes with their children can restore local BST property without full rebuild.

3. Step 3: Evaluate other options

   Perform an in-order traversal, collect values, then rebuild the BST from sorted values. rebuilds fully, Delete all nodes and insert them again in correct order. deletes all nodes (costly), Ignore the violations as they do not affect search operations. ignores problem (wrong).

4. Final Answer:

   Swap the values of the violating nodes with their children to restore BST property locally. -> Option A

5. Quick Check:

   Local swaps fix BST violations efficiently [OK]

Hint: Fix BST by swapping violating node values locally [OK]

Common Mistakes:

• Rebuilding entire tree unnecessarily
• Ignoring violations thinking no impact
• Deleting all nodes instead of fixing