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.