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.