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.