Why BST Over Plain Binary Tree in DSA C++ - 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 preferred for searching?

A BST keeps elements in sorted order, allowing faster search using the tree structure.

B BST uses less memory than a plain binary tree because it stores fewer nodes.

C BST allows duplicate values while plain binary tree does not.

D BST nodes have more children than plain binary tree nodes, making search faster.

💡 Hint

Think about how the order of elements affects the speed of finding a value.

A BST keeps nodes in sorted order so that at each step you can decide to go left or right, reducing search time to O(log n) on average. A plain binary tree has no order, so searching may require checking every node.

❓ Predict Output

intermediate

Output of Searching in BST vs Plain Binary Tree

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

DSA C++

struct Node {
  int val;
  Node* left;
  Node* right;
};

// Plain binary tree search (DFS)
bool searchPlain(Node* root, int target) {
  if (!root) return false;
  if (root->val == target) return true;
  return searchPlain(root->left, target) || searchPlain(root->right, target);
}

// BST search
bool searchBST(Node* root, int target) {
  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);
}

// Assume tree is built with nodes: 5 (root), 3 (left), 7 (right)

A Both searchPlain and searchBST return false.

B Both searchPlain and searchBST return true.

C searchPlain returns true, searchBST returns false.

D searchPlain returns false, searchBST returns true.

💡 Hint

Both functions check if the value 7 exists in the tree.

Both searchPlain and searchBST will find the value 7 in the tree. searchPlain does a full search, searchBST uses the BST property to find it faster.

❓ Predict Output

advanced

Resulting Tree Structure After Insertions in BST vs Plain Binary Tree

Consider inserting values 10, 5, 15, 3, 7 into an empty tree. What is the printed in-order traversal output for a BST and a plain binary tree where nodes are inserted as left child if empty, else right child?

DSA C++

// In-order traversal prints nodes in sorted order for BST
// Plain binary tree inserts nodes always to left if empty, else right
// Insert order: 10, 5, 15, 3, 7
// Print in-order traversal after insertions

A BST: 3 -> 5 -> 7 -> 10 -> 15 -> null; Plain: 3 -> 5 -> 7 -> 10 -> 15 -> null

B BST: 10 -> 5 -> 3 -> 7 -> 15 -> null; Plain: 3 -> 5 -> 7 -> 10 -> 15 -> null

C BST: 3 -> 5 -> 7 -> 10 -> 15 -> null; Plain: 10 -> 5 -> 3 -> 7 -> 15 -> null

D BST: 10 -> 5 -> 3 -> 7 -> 15 -> null; Plain: 10 -> 5 -> 3 -> 7 -> 15 -> null

💡 Hint

Remember BST in-order traversal prints sorted values. Plain binary tree insertion order affects traversal.

BST in-order traversal prints sorted values: 3,5,7,10,15. Plain binary tree insertion as left if empty else right creates a skewed tree, so in-order prints nodes in insertion order.

🔧 Debug

advanced

Why does searching in a plain binary tree take longer than in a BST?

Given the code below, why does searching for a value in a plain binary tree take longer than in a BST?

DSA C++

bool searchPlain(Node* root, int target) {
  if (!root) return false;
  if (root->val == target) return true;
  return searchPlain(root->left, target) || searchPlain(root->right, target);
}

bool searchBST(Node* root, int target) {
  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 binary tree search uses more memory, causing slower performance.

B Plain binary tree search uses recursion; BST search uses iteration, making it faster.

C Plain binary tree search only checks left children; BST search checks both children.

D Plain binary tree search checks all nodes because it has no order; BST search uses order to skip half the nodes.

💡 Hint

Think about how the tree structure affects the number of nodes checked.

Plain binary tree has no ordering, so search may visit every node. BST uses ordering to decide which branch to search, reducing nodes visited.

🚀 Application

expert

Choosing Data Structure for Fast Lookup in Large Dataset

You need to store a large dataset of unique numbers and perform many search queries. Which data structure is best and why?

A Use a Binary Search Tree because it keeps data sorted and allows O(log n) average search time.

B Use a plain Binary Tree because it is simpler to implement and uses less memory.

C Use a Linked List because it allows easy insertion and deletion.

D Use an unsorted array because searching is faster without ordering overhead.

💡 Hint

Consider search time complexity and data ordering.

BST provides efficient O(log n) average search time by keeping data sorted. Plain binary tree and linked list have O(n) search time. Unsorted array also requires O(n) search.

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

   A BST stores elements so that left child nodes are smaller and right child nodes are larger than the parent node, maintaining sorted order.

2. Step 2: Compare search efficiency

   This sorted structure allows searching by comparing values and moving left or right, reducing search time to O(log n) on average, unlike a plain Binary Tree which has no order and requires O(n) search.

3. Final Answer:

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

4. Quick Check:

   BST sorted order = faster search [OK]

Hint: BST sorts nodes for quick search, plain tree does not [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare a node structure for a BST in C++?

easy

A. struct Node { int data; Node* parent; };

B. struct Node { int data; Node* left; Node* right; };

C. struct Node { int data; Node left; Node right; };

D. struct Node { int data; Node* next; };

Solution

1. Step 1: Identify correct pointer usage for children

   A BST node must have pointers to left and right child nodes, so Node* left and Node* right are needed.

2. Step 2: Check each option

   struct Node { int data; Node* left; Node* right; }; correctly declares pointers to left and right children. struct Node { int data; Node left; Node right; }; incorrectly uses Node left and right (not pointers). struct Node { int data; Node* parent; }; only has parent pointer, missing children. struct Node { int data; Node* next; }; uses next pointer which is for linked lists, not BST.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option B

4. Quick Check:

   BST node needs left and right pointers [OK]

Hint: BST nodes have left and right child pointers [OK]

Common Mistakes:

• Using objects instead of pointers for children
• Confusing parent pointer with child pointers
• Using 'next' pointer like in linked lists

3. Consider the following code inserting values into a BST:

#include <iostream>

struct Node {
  int data;
  Node* left;
  Node* right;
};

Node* insert(Node* root, int val) {
  if (!root) {
    Node* n = new Node{val, nullptr, nullptr};
    return n;
  }
  if (val < root->data) root->left = insert(root->left, val);
  else root->right = insert(root->right, val);
  return root;
}

void inorder(Node* node) {
  if (!node) return;
  inorder(node->left);
  std::cout << node->data << " ";
  inorder(node->right);
}

int main() {
  Node* root = nullptr;
  root = insert(root, 10);
  root = insert(root, 5);
  root = insert(root, 15);
  root = insert(root, 7);
  inorder(root);
  return 0;
}

What is the output of the inorder traversal?

medium

A. 10 5 7 15

B. 15 10 7 5

C. 5 7 10 15

D. 7 5 10 15

Solution

1. Step 1: Understand insertion order and BST property

   Values inserted are 10 (root), 5 (left of 10), 15 (right of 10), 7 (right of 5). BST property keeps left < parent < right.

2. Step 2: Perform inorder traversal

   Inorder traversal visits left subtree, node, then right subtree. So nodes visited in order: 5, 7, 10, 15.

3. Final Answer:

   5 7 10 15 -> Option C

4. Quick Check:

   Inorder traversal of BST = sorted order [OK]

Hint: Inorder traversal of BST prints sorted values [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Misplacing 7 as left child of 10
• Ignoring BST insertion rules

4. The following code attempts to insert a value into a BST but has a bug:

Node* insert(Node* root, int val) {
  if (root == nullptr) {
    Node* n = new Node{val, nullptr, nullptr};
    return n;
  }
  if (val <= root->data) {
    insert(root->left, val);
  } else {
    insert(root->right, val);
  }
  return root;
}

What is the bug and how to fix it?

medium

A. The recursive calls do not assign returned nodes to root's children; fix by root->left = insert(root->left, val) and root->right = insert(root->right, val)

B. The base case is wrong; should check if val == root->data

C. The function should return void instead of Node*

D. The comparison should be val < root->data instead of val <= root->data

Solution

1. Step 1: Identify missing assignment in recursion

   The recursive calls insert(root->left, val) and insert(root->right, val) do not update root's left or right pointers with the returned new nodes.

2. Step 2: Fix by assigning returned nodes

   Assign the recursive call results back: root->left = insert(root->left, val); root->right = insert(root->right, val); so the tree links update correctly.

3. Final Answer:

   The recursive calls do not assign returned nodes to root's children; fix by root->left = insert(root->left, val) and root->right = insert(root->right, val) -> Option A

4. Quick Check:

   Assign recursive insert results to children [OK]

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

Common Mistakes:

• Ignoring returned node from recursion
• Changing base case unnecessarily
• Changing comparison operator without reason

5. You have a plain Binary Tree and a BST both containing the same 7 unique values. You want to find if a value exists in the tree. Which of the following statements best explains why searching in the BST is generally faster than in the plain Binary Tree?

hard

A. BST uses hashing internally to find values instantly

B. BST stores values in a linked list internally, making search O(1)

C. Plain Binary Tree nodes have no pointers, so search is impossible

D. BST allows skipping half of the nodes at each step due to ordering, reducing search time to O(log n) on average

Solution

1. Step 1: Understand search in BST vs plain Binary Tree

   BST maintains sorted order so at each node, you decide to go left or right, effectively halving the search space each step.

2. Step 2: Compare time complexities

   This halving leads to average search time O(log n). Plain Binary Tree has no order, so search may check every node, O(n) time.

3. Final Answer:

   BST allows skipping half of the nodes at each step due to ordering, reducing search time to O(log n) on average -> Option D

4. Quick Check:

   BST halves search space each step [OK]

Hint: BST halves search space; plain tree searches all nodes [OK]

Common Mistakes:

• Thinking BST uses linked lists internally
• Believing plain Binary Tree has no pointers
• Assuming BST uses hashing