Why BST Over Plain Binary Tree in DSA C++ - Why This Pattern

Mental Model

A Binary Search Tree (BST) keeps data sorted so we can find things fast, unlike a plain binary tree which has no order.

Analogy: Imagine a phone book: a BST is like a phone book sorted by names so you can quickly find a contact, while a plain binary tree is like a random pile of papers where you have to check each one.

Plain Binary Tree:
      5
     / \
    3   8
   /   / \
  7   1   9

BST:
      5
     / \
    3   8
   /     \
  1       9

Dry Run Walkthrough

Input: Plain binary tree with nodes 5,3,8,7,1,9; search for 7 BST with nodes 5,3,8,1,9; search for 7

Goal: Show how searching for 7 is slower in plain binary tree and faster in BST

Step 1: Start search at root node 5 in plain binary tree

Plain BT: [5] -> 3 -> 8 -> 7 -> 1 -> 9
BST: [5] -> 3 -> 8 -> 1 -> 9

Why: We start at the root to look for 7

Step 2: In plain binary tree, check left child 3 (not 7), then right child 8 (not 7)

Plain BT: 5 -> [3] -> 8 -> 7 -> 1 -> 9
BST: 5 -> [3] -> 8 -> 1 -> 9

Why: No order, so we must check both sides

Step 3: In plain binary tree, check left child of 3 which is 7 (found)

Plain BT: 5 -> 3 -> [7] -> 1 -> 9
BST: 5 -> 3 -> 8 -> 1 -> 9

Why: We found 7 but had to check multiple nodes

Step 4: In BST, compare 7 with root 5; since 7 > 5, go right to 8

BST: 5 -> 3 -> [8] -> 1 -> 9
Plain BT: 5 -> 3 -> 7 -> 1 -> 9

Why: BST uses order to decide direction

Step 5: Compare 7 with 8; since 7 < 8, go left child which is null (7 not found)

BST: 5 -> 3 -> 8 -> null
Plain BT: 5 -> 3 -> 7 -> 1 -> 9

Why: BST quickly concludes 7 is not in tree without checking all nodes

Result:

Plain Binary Tree final state: 5 -> 3 -> 7 -> 1 -> 9 (7 found after multiple checks)
BST final state: 5 -> 3 -> 8 -> 1 -> 9 (7 not found quickly by skipping unnecessary nodes)

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

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

// BST search (uses order)
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);
}

int main() {
    // Plain binary tree construction
    Node* plainRoot = new Node(5);
    plainRoot->left = new Node(3);
    plainRoot->right = new Node(8);
    plainRoot->left->left = new Node(7);
    plainRoot->right->left = new Node(1);
    plainRoot->right->right = new Node(9);

    // BST construction
    Node* bstRoot = new Node(5);
    bstRoot->left = new Node(3);
    bstRoot->right = new Node(8);
    bstRoot->left->left = new Node(1);
    bstRoot->right->right = new Node(9);

    int target = 7;

    cout << "Plain Binary Tree search for " << target << ": " << (searchPlain(plainRoot, target) ? "Found" : "Not Found") << endl;
    cout << "BST search for " << target << ": " << (searchBST(bstRoot, target) ? "Found" : "Not Found") << endl;

    return 0;
}

if (!root) return false;

stop search if node is null

if (root->val == target) return true;

found target node

if (searchPlain(root->left, target)) return true;

search left subtree in plain binary tree

return searchPlain(root->right, target);

search right subtree if not found in left

if (target < root->val) return searchBST(root->left, target);

go left if target less than current node in BST

else return searchBST(root->right, target);

go right if target greater or equal in BST

Output

Plain Binary Tree search for 7: Found

BST search for 7: Not Found

Complexity Analysis

Time: O(n) for plain binary tree because it may check every node; O(h) for BST where h is tree height because it skips half the nodes each step

Space: O(h) for recursion stack in both, where h is height of tree

vs Alternative: BST is faster than plain binary tree for search because it uses ordering to skip unnecessary nodes, reducing time from linear to logarithmic in balanced trees

Edge Cases

Empty tree

Search returns false immediately

DSA C++

if (!root) return false;

Target is root node

Search returns true immediately

DSA C++

if (root->val == target) return true;

Target not present in tree

Search explores necessary nodes and returns false

DSA C++

return searchPlain(root->right, target);

When to Use This Pattern

When you need fast search in a tree and the data can be kept sorted, reach for BST because it uses order to reduce search time.

Common Mistakes

Mistake: Trying to search a BST like a plain binary tree by checking both children always
Fix: Use the BST property to decide to go left or right based on comparison with current node

Mistake: Assuming BST search always finds the target even if not present
Fix: Return false when reaching null node to indicate target not found

Summary

Shows why BST is better than plain binary tree for searching by using order to skip nodes.

Use BST when you want faster search, insert, and delete operations on sorted data.

The key insight is BST keeps nodes ordered so you only explore one path, not the whole tree.

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