Why BST Over Plain Binary Tree in DSA Javascript - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why is a Binary Search Tree (BST) preferred over a plain Binary Tree for searching?

Consider you want to find a number in a tree structure. Which reason best explains why a BST is better than a plain Binary Tree for this task?

A BST stores elements randomly, so it uses less memory than a plain Binary Tree.

B BST keeps elements sorted, so searching can skip half the tree at each step, making it faster.

C BST allows duplicate values easily, unlike a plain Binary Tree.

D BST nodes have more children than a plain Binary Tree, so it is wider.

💡 Hint

Think about how sorting helps in quickly finding a number.

A BST keeps its elements in order so that at each node, you know if the number you want is smaller or larger. This lets you ignore half the tree at every step, making search faster than in a plain Binary Tree where elements are unordered.

❓ Predict Output

intermediate

Output of Searching in BST vs Plain Binary Tree

Given the following trees, what will be the output of searching for value 7?

BST structure: 5 (root), left child 3, right child 8, left child of 3 is 2, right child of 3 is 4, left child of 8 is 7

Plain Binary Tree structure: 5 (root), left child 8, right child 3, left child of 8 is 7, right child of 3 is 2

Assume search returns 'Found' if value exists, else 'Not Found'.

DSA Javascript

function searchBST(node, val) {
  if (!node) return 'Not Found';
  if (node.val === val) return 'Found';
  if (val < node.val) return searchBST(node.left, val);
  else return searchBST(node.right, val);
}

function searchPlainBT(node, val) {
  if (!node) return 'Not Found';
  if (node.val === val) return 'Found';
  return searchPlainBT(node.left, val) === 'Found' ? 'Found' : searchPlainBT(node.right, val);
}

// Outputs:
// A: searchBST(rootBST, 7) and searchPlainBT(rootPlainBT, 7)
// B: searchBST(rootBST, 7) only
// C: searchPlainBT(rootPlainBT, 7) only
// D: Neither finds 7

A Both searchBST and searchPlainBT return 'Found'

B Only searchBST returns 'Found', searchPlainBT returns 'Not Found'

C Only searchPlainBT returns 'Found', searchBST returns 'Not Found'

D Both return 'Not Found'

💡 Hint

Check if 7 exists in both trees.

Both trees contain the value 7. The BST search uses ordering to find it efficiently. The plain binary tree search checks all nodes recursively and also finds 7.

🔧 Debug

advanced

Why does this BST search code fail on some inputs?

Look at this JavaScript function to search a BST. It sometimes returns 'Not Found' even when the value exists. Why?

DSA Javascript

function searchBST(node, val) {
  if (!node) return 'Not Found';
  if (node.val === val) return 'Found';
  if (val < node.val) return searchBST(node.left, val);
  else return searchBST(node.right, val);
}

A Using '<=' causes the search to go left even when val equals node.val, missing the correct node.

B The function should check right child first before left child.

C The base case is wrong; it should return null instead of 'Not Found'.

D The function does not handle empty trees properly.

💡 Hint

Think about what happens when val equals node.val.

Using '<=' means if val equals node.val, the function goes left instead of returning 'Found'. This causes it to miss the node with the value and eventually return 'Not Found'.

🚀 Application

advanced

Choosing Data Structure for Fast Lookup and Ordered Data

You need to store a list of unique numbers and frequently check if a number exists and also get numbers in sorted order. Which data structure is best?

A Use a linked list because it keeps insertion order and is easy to search.

B Use a plain Binary Tree because it is simpler and faster for all operations.

C Use a Binary Search Tree (BST) because it supports fast search and keeps data sorted.

D Use an unsorted array because searching is faster with linear scan.

💡 Hint

Think about how to get sorted data and fast search together.

A BST keeps data sorted and allows searching in O(log n) time on average. Plain binary trees and linked lists do not keep data sorted, and arrays require linear search unless sorted and maintained carefully.

🧠 Conceptual

expert

Why can a BST degrade to a plain Binary Tree in worst cases?

What causes a BST to behave like a plain Binary Tree with slow search times?

A Searching for values not in the tree converts it into a plain Binary Tree.

B Deleting nodes randomly causes the BST to lose its structure.

C Using duplicate values causes the BST to become unordered.

D Inserting elements in sorted order creates a skewed tree, losing the balanced property.

💡 Hint

Think about how insertion order affects tree shape.

If elements are inserted in sorted order, the BST becomes skewed like a linked list, making search time O(n) instead of O(log n). This is why balanced BSTs or self-balancing trees are used.

Practice

1. Why is a Binary Search Tree (BST) preferred over a plain Binary Tree for searching operations?

easy

A. BST does not require pointers to child nodes.

B. BST uses less memory than a plain Binary Tree.

C. BST nodes can have more than two children.

D. BST allows faster search by maintaining sorted order of elements.

Solution

1. Step 1: Understand the structure difference

   A BST keeps elements in sorted order where left child is smaller and right child is larger, unlike a plain Binary Tree which has no order.

2. Step 2: Analyze search efficiency

   Because of this order, BST allows searching by comparing and moving left or right, reducing search time to O(log n) on average, while plain Binary Tree search is O(n).

3. Final Answer:

   BST allows faster search by maintaining sorted order of elements. -> Option D

4. Quick Check:

   BST sorted order = faster search [OK]

Hint: BST keeps order for quick search decisions [OK]

Common Mistakes:

• Thinking BST uses less memory than plain Binary Tree
• Confusing number of children in BST
• Assuming BST nodes don't have child pointers

2. Which of the following is the correct way to check if a node's value is less than the root's value in JavaScript BST code?

easy

A. if (node.value < root.value) {}

B. if node.value < root.value {}

C. if (node.value << root.value) {}

D. if node.value < root.value then {}

Solution

1. Step 1: Identify correct JavaScript syntax for if statement

   JavaScript requires parentheses around the condition and curly braces for the block.

2. Step 2: Check comparison operator and syntax

   The less than operator is <, and it must be inside parentheses: if (condition) {} is correct.

3. Final Answer:

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

4. Quick Check:

   Correct if syntax = if (node.value < root.value) {} [OK]

Hint: Use parentheses and curly braces in if statements [OK]

Common Mistakes:

• Omitting parentheses around condition
• Using incorrect operators like <<
• Writing if without parentheses or braces

3. What will be the output of the following code snippet that inserts values into a BST and then performs an in-order traversal?

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;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }
  inOrder(node, result = []) {
    if (node) {
      this.inOrder(node.left, result);
      result.push(node.value);
      this.inOrder(node.right, result);
    }
    return result;
  }
}

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

medium

A. [5, 7, 10, 15]

B. [10, 5, 7, 15]

C. [15, 10, 7, 5]

D. [7, 5, 10, 15]

Solution

1. Step 1: Insert nodes into BST

   Insert 10 as root, 5 to left of 10, 15 to right of 10, 7 to right of 5.

2. Step 2: Perform in-order traversal

   In-order visits left subtree, root, then right subtree. So order is 5, 7, 10, 15.

3. Final Answer:

   [5, 7, 10, 15] -> Option A

4. Quick Check:

   In-order BST traversal = sorted values [OK]

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

Common Mistakes:

• Confusing traversal order
• Inserting nodes incorrectly
• Expecting pre-order or post-order output

4. The following code attempts to insert a value into a BST but causes an infinite loop. What is the error?

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;
        break;
      } else {
        current = current.left;
      }
    } else {
      if (!current.right) {
        current.right = newNode;
        break;
      } else {
        current = current.right;
      }
    }
  }
}

medium

A. New node is not created properly.

B. Incorrect comparison operator used.

C. Missing break statement after inserting new node.

D. Root node is not initialized.

Solution

1. Step 1: Analyze loop behavior after insertion

   After assigning newNode to left or right child, loop continues without break, causing infinite loop.

2. Step 2: Identify missing break

   Adding break after insertion stops the loop and prevents infinite iteration.

3. Final Answer:

   Missing break statement after inserting new node. -> Option C

4. Quick Check:

   Break after insert stops infinite loop [OK]

Hint: Add break after insertion to exit loop [OK]

Common Mistakes:

• Forgetting break after insertion
• Changing comparison operators unnecessarily
• Assuming new node creation is faulty

5. You want to store a large set of numbers and perform frequent searches. Why would using a balanced BST be better than a plain Binary Tree or an unbalanced BST?

hard

A. Balanced BST uses less memory than unbalanced BST.

B. Balanced BST guarantees O(log n) search time, unlike unbalanced BST or plain Binary Tree.

C. Balanced BST allows nodes to have multiple parents for faster access.

D. Balanced BST does not require pointers to child nodes.

Solution

1. Step 1: Understand search time in different trees

   Plain Binary Tree search is O(n), unbalanced BST can degrade to O(n) if skewed, balanced BST keeps height low.

2. Step 2: Benefit of balanced BST

   Balanced BST maintains height around log n, ensuring search, insert, delete operations are O(log n) consistently.

3. Final Answer:

   Balanced BST guarantees O(log n) search time, unlike unbalanced BST or plain Binary Tree. -> Option B

4. Quick Check:

   Balanced BST = consistent fast search [OK]

Hint: Balance keeps tree height low for fast search [OK]

Common Mistakes:

• Thinking balanced BST uses less memory
• Believing nodes can have multiple parents
• Assuming no child pointers needed