Why BST Over Plain Binary Tree in DSA Typescript - 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 have two trees: a plain binary tree and a binary search tree (BST). Which reason best explains why BST is better for searching?

A BST keeps elements sorted, so searching can skip half the tree at each step.

B BST nodes have more children than a plain binary tree.

C BST allows storing duplicate values easily.

D BST uses less memory than a plain binary tree.

💡 Hint

Think about how the order of elements helps in finding a value quickly.

A BST keeps its elements in sorted order, so when searching for a value, you can decide to go left or right based on comparison, effectively skipping half the nodes each time. This makes searching faster than in a plain binary tree, where nodes are unordered.

❓ Predict Output

intermediate

Output of Searching in BST vs Plain Binary Tree

Given the following TypeScript code snippets for searching a value in a plain binary tree and a BST, what is the output when searching for value 7?

DSA Typescript

class Node {
  constructor(public val: number, public left: Node | null = null, public right: Node | null = null) {}
}

// Plain binary tree search (no order)
function searchPlain(root: Node | null, target: number): boolean {
  if (!root) return false;
  if (root.val === target) return true;
  return searchPlain(root.left, target) || searchPlain(root.right, target);
}

// BST search (ordered)
function searchBST(root: Node | null, target: number): boolean {
  if (!root) return false;
  if (root.val === target) return true;
  if (target < root.val) return searchBST(root.left, target);
  else return searchBST(root.right, target);
}

// Tree setup
const rootPlain = new Node(5, new Node(3, new Node(7)), new Node(8));
const rootBST = new Node(5, new Node(3), new Node(8, new Node(7)));

console.log(searchPlain(rootPlain, 7));
console.log(searchBST(rootBST, 7));

A false false

B false true

C true false

D true true

💡 Hint

Check if both search functions find the value 7 in their respective trees.

Both searchPlain and searchBST find the value 7 in their trees, so both print true.

🔧 Debug

advanced

Why does this plain binary tree search take longer than BST search?

Look at the two search functions below. Why does the plain binary tree search take longer time than the BST search?

DSA Typescript

function searchPlain(root: Node | null, target: number): boolean {
  if (!root) return false;
  if (root.val === target) return true;
  return searchPlain(root.left, target) || searchPlain(root.right, target);
}

function searchBST(root: Node | null, target: number): boolean {
  if (!root) return false;
  if (root.val === target) return true;
  if (target < root.val) return searchBST(root.left, target);
  else return searchBST(root.right, target);
}

A Plain tree search uses more memory; BST search uses less memory.

B Plain tree search checks all nodes; BST search skips half nodes by ordering.

C Plain tree search uses loops; BST search uses recursion.

D Plain tree search only works on balanced trees; BST search works on all trees.

💡 Hint

Think about how many nodes each search visits in worst case.

Plain binary tree search may visit every node because it has no order, while BST search uses the order to decide which subtree to search, skipping half the nodes on average.

📝 Syntax

advanced

Identify the error in this BST insertion code

Which option correctly fixes the syntax error in this TypeScript BST insertion function?

DSA Typescript

function insertBST(root: Node | null, val: number): Node {
  if (!root) return new Node(val);
  if (val < root.val) {
    root.left = insertBST(root.left, val)
  } else {
    root.right = insertBST(root.right, val);
  }
  return root;
}

A Remove the return statement at the end

B Change 'if' to 'while' in the first condition

C Add missing semicolon after root.left = insertBST(root.left, val)

D Replace 'else' with 'else if (val > root.val)'

💡 Hint

Look carefully at the line endings and TypeScript syntax rules.

The line 'root.left = insertBST(root.left, val)' is missing a semicolon, causing a syntax error. Adding it fixes the code.

🚀 Application

expert

How many nodes are visited when searching for 15 in this BST?

Given the BST below, how many nodes are visited when searching for the value 15?

BST structure:

• Root: 10
• Left child of 10: 5
• Right child of 10: 20
• Left child of 20: 15
• Right child of 20: 25

A 3

B 2

C 4

D 5

💡 Hint

Count nodes visited from root to the target following BST search rules.

Search visits nodes 10, then 20, then 15, totaling 3 nodes.

Practice

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

easy

A. Because BST keeps elements in sorted order allowing faster search

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

C. Because BST nodes can have more than two children

D. Because BST does not require pointers to child nodes

Solution

1. Step 1: Understand the structure of BST vs plain Binary Tree

   A BST stores nodes so that left child is smaller and right child is larger, keeping data sorted. A plain Binary Tree has no order.

2. Step 2: Analyze search efficiency

   Because BST is sorted, searching can skip half the tree at each step, making it faster than searching a plain Binary Tree which may require checking all nodes.

3. Final Answer:

   Because BST keeps elements in sorted order allowing faster search -> Option A

4. Quick Check:

   Sorted structure = faster search [OK]

Hint: BST is sorted, plain tree is not, so search is faster [OK]

Common Mistakes:

• Thinking BST uses less memory
• Confusing number of children in BST
• Assuming BST has no pointers

2. Which of the following is the correct TypeScript syntax to declare a node in a Binary Search Tree?

easy

A. class Node { value: number; left: Node | null; right: Node | null; }

B. function Node(value) { this.value = value; this.left = null; this.right = null; }

C. interface Node { value: string; left: Node; right: Node; }

D. type Node = { value: number; left?: Node; right?: Node }

Solution

1. Step 1: Identify correct TypeScript class syntax for BST node

   class Node { value: number; left: Node | null; right: Node | null; } correctly declares a class with value and nullable left and right nodes using TypeScript types.

2. Step 2: Check other options for correctness

   function Node(value) { this.value = value; this.left = null; this.right = null; } is JavaScript function style, not TypeScript class. interface Node { value: string; left: Node; right: Node; } uses string value and non-nullable children which is incorrect. type Node = { value: number; left?: Node; right?: Node } uses optional children but is a type alias, not a class.

3. Final Answer:

   class Node { value: number; left: Node | null; right: Node | null; } -> Option A

4. Quick Check:

   TypeScript class with nullable children = class Node { value: number; left: Node | null; right: Node | null; } [OK]

Hint: Look for TypeScript class with nullable left/right nodes [OK]

Common Mistakes:

• Confusing JavaScript function with TypeScript class
• Using non-nullable children causing errors
• Using wrong value types

3. Given the following BST insertion code snippet, what will be the in-order traversal output after inserting values 10, 5, 15, 3, 7?

medium

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

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

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

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

Solution

1. Step 1: Insert values into BST in given order

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

2. Step 2: Perform in-order traversal (left, root, right)

   Traverse left subtree: 3, 5, 7; then root 10; then right subtree 15. Combined: [3, 5, 7, 10, 15]

3. Final Answer:

   [3, 5, 7, 10, 15] -> Option D

4. Quick Check:

   In-order traversal of BST = sorted values [OK]

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

Common Mistakes:

• Confusing traversal order
• Inserting nodes incorrectly
• Mixing up left and right children

4. Identify the bug in this BST insertion function snippet in TypeScript:

function insert(root: Node | null, val: number): Node {
  if (!root) return new Node(val);
  if (val < root.value) insert(root.left, val);
  else insert(root.right, val);
  return root;
}

medium

A. Node constructor is called without new keyword

B. Missing return statements for recursive calls

C. Incorrect comparison operator for BST insertion

D. Function does not handle duplicate values

Solution

1. Step 1: Analyze recursive calls in insertion

   The recursive calls insert(root.left, val) and insert(root.right, val) do not assign the returned node back to root.left or root.right.

2. Step 2: Identify missing return assignments

   Without assigning, the tree structure does not update. Correct code should be root.left = insert(root.left, val) and root.right = insert(root.right, val).

3. Final Answer:

   Missing return statements for recursive calls -> Option B

4. Quick Check:

   Recursive insert must update child links [OK]

Hint: Always assign recursive insert results to child nodes [OK]

Common Mistakes:

• Not assigning recursive call results
• Using wrong comparison operators
• Ignoring duplicates silently

5. You have a plain Binary Tree and a BST both containing the same values. Which operation benefits the most from using the BST instead of the plain Binary Tree, and why?

hard

A. Traversing all nodes, because BST traversal is faster than plain tree traversal

B. Inserting a new value, because BST insertion is always O(1)

C. Searching for a value, because BST allows O(log n) average time search

D. Deleting a node, because BST deletion never requires rebalancing

Solution

1. Step 1: Compare searching in BST vs plain Binary Tree

   BST keeps nodes sorted, enabling binary search-like behavior with average O(log n) time. Plain Binary Tree has no order, so search is O(n).

2. Step 2: Evaluate other operations

   Insertion in BST is not always O(1), deletion may require rebalancing, and traversal visits all nodes in both trees equally.

3. Final Answer:

   Searching for a value, because BST allows O(log n) average time search -> Option C

4. Quick Check:

   BST speeds up search, not insertion or traversal [OK]

Hint: BST speeds up search, not insertion or traversal [OK]

Common Mistakes:

• Thinking insertion is always O(1)
• Assuming deletion never needs rebalancing
• Believing traversal is faster in BST