Why BST Over Plain Binary Tree in DSA C++ - Why It Was Designed This Way

Overview - Why BST Over Plain Binary Tree

What is it?

A Binary Tree is a structure where each node has up to two children, but the order of values is not fixed. A Binary Search Tree (BST) is a special kind of binary tree where every node's left child has a smaller value and the right child has a larger value. This order helps us find, add, or remove values faster than in a plain binary tree. BSTs keep data sorted and allow quick searching.

Why it matters

Without the order rules of a BST, searching for a value in a plain binary tree can take a long time because you might have to check every node. BSTs solve this by organizing data so you can skip large parts of the tree when searching. This makes programs faster and more efficient, especially when working with large amounts of data like phone books, databases, or game leaderboards.

Where it fits

Before learning about BSTs, you should understand what a binary tree is and how nodes connect. After BSTs, you can learn about balanced trees like AVL or Red-Black Trees, which keep BSTs efficient even when many insertions and deletions happen.

Mental Model

Core Idea

A BST is a binary tree organized so that left children are smaller and right children are larger, enabling fast searching and sorting.

Think of it like...

Imagine a library where books are arranged so that all books with titles starting with A to M are on the left shelves and N to Z on the right shelves. This order helps you find a book quickly without checking every shelf.

       [Root]
       /    \
  [Smaller]  [Larger]
    /  \       /  \
 ...  ...   ...  ...

Build-Up - 7 Steps

1

Foundation

Understanding Plain Binary Trees

Concept: Learn what a binary tree is and how nodes connect without any order.

A binary tree is a structure where each node can have up to two children called left and right. There is no rule about the values stored; they can be random. For example, a root node with value 10 might have left child 5 and right child 20, but the left child could also be 15 if we don't follow any order.

Result

You get a tree where nodes connect but values are unordered, making searching slow.

Understanding the basic structure of binary trees is essential before adding rules that improve efficiency.

2

Foundation

Searching in Plain Binary Trees

Concept: Explore how to find a value in a binary tree without order.

To find a value, you must check the root, then recursively check left and right children until you find the value or reach the end. This can mean visiting every node in the worst case.

Result

Searching can take time proportional to the number of nodes, which is slow for large trees.

Knowing the inefficiency of searching unordered trees motivates the need for better structures.

3

Intermediate

Introducing Binary Search Tree Rules

Concept: Learn the ordering rule that defines a BST and how it changes searching.

In a BST, every node's left child has a smaller value, and the right child has a larger value. This rule applies recursively to all nodes. For example, if the root is 10, left children must be less than 10, right children greater than 10.

Result

The tree is organized so that searching can skip half the nodes at each step.

This ordering rule is the key to making searching much faster than in plain binary trees.

4

Intermediate

Searching in a BST

🤔Before reading on: do you think searching in a BST always checks every node like in a plain binary tree? Commit to yes or no.

Concept: Understand how the BST order speeds up searching.

To find a value, start at the root. If the value is smaller, go left; if larger, go right. Repeat until you find the value or reach a leaf. This way, you ignore half the tree at each step, like binary search in a list.

Result

Searching takes time proportional to the height of the tree, often much faster than checking every node.

Knowing how BST order guides searching helps you see why BSTs are efficient for lookups.

5

Intermediate

Insertion and Deletion in BSTs

🤔Before reading on: do you think inserting a new value in a BST requires reordering the entire tree? Commit to yes or no.

Concept: Learn how to add and remove values while keeping BST order.

To insert, start at the root and follow the BST rules to find the correct empty spot. To delete, if the node has no or one child, remove or replace it easily. If it has two children, replace it with the smallest value in the right subtree to keep order.

Result

You can add or remove values without breaking the BST structure.

Understanding insertion and deletion shows how BSTs maintain order dynamically.

6

Advanced

Why BSTs Are Faster Than Plain Trees

🤔Before reading on: do you think BSTs always guarantee fast operations regardless of insertion order? Commit to yes or no.

Concept: Explore how BST order reduces search time and when it might fail.

BSTs reduce search time from checking all nodes to roughly the tree height. However, if inserted in sorted order, the tree becomes a linked list, losing speed. Balanced BSTs fix this, but plain BSTs still improve average cases over unordered trees.

Result

BSTs usually speed up searching, insertion, and deletion compared to plain trees, but worst cases exist.

Knowing BST strengths and weaknesses helps you choose the right tree type for your needs.

7

Expert

BST Use in Real Systems and Limitations

🤔Before reading on: do you think BSTs are always the best choice for all search problems? Commit to yes or no.

Concept: Understand practical uses and when to prefer other data structures.

BSTs are used in databases, file systems, and memory indexing where ordered data is needed. However, for guaranteed speed, balanced trees or hash tables are preferred. BSTs are simple and good for moderate data sizes or when data arrives randomly.

Result

You learn when BSTs shine and when other structures are better.

Knowing BST practical limits prevents misuse and guides better data structure choices.

Under the Hood

A BST stores nodes with pointers to left and right children. Each node's value divides the tree into smaller and larger parts. Searching compares the target value to the current node and moves left or right accordingly. This reduces the search space exponentially. Insertions and deletions adjust pointers to maintain this order without rearranging the entire tree.

Why designed this way?

BSTs were designed to combine the simplicity of binary trees with the efficiency of binary search. Early computer scientists needed a way to keep data sorted and searchable without the overhead of arrays or linked lists. The BST structure balances ease of insertion with faster lookup times, trading off complexity for performance.

          [Node]
          /    \
   [Left < Node] [Right > Node]
       /  \          /   \
  ...    ...     ...     ...

Myth Busters - 4 Common Misconceptions

Quick: Does a BST always guarantee O(log n) search time? Commit to yes or no.

Common Belief: BSTs always provide fast O(log n) search times no matter what.

Reality: BSTs can degrade to O(n) time if nodes are inserted in sorted order, making the tree unbalanced.

Why it matters: Assuming always fast searches can lead to poor performance in real applications if the tree becomes skewed.

Quick: Is a plain binary tree just as good as a BST for searching? Commit to yes or no.

Common Belief: A plain binary tree is just as efficient as a BST for searching values.

Reality: Plain binary trees have no order, so searching may require checking every node, which is slower than BSTs.

Why it matters: Using plain binary trees for search-heavy tasks wastes time and resources.

Quick: Can you insert a new value anywhere in a BST without breaking its rules? Commit to yes or no.

Common Belief: You can insert a new value anywhere in a BST and still keep it valid.

Reality: Insertion must follow BST rules; placing a value incorrectly breaks the order and search efficiency.

Why it matters: Incorrect insertion leads to invalid BSTs and broken search logic.

Quick: Does deleting a node in a BST always remove it without affecting the tree structure? Commit to yes or no.

Common Belief: Deleting any node in a BST is simple and doesn't affect the rest of the tree.

Reality: Deleting nodes with two children requires careful replacement to maintain BST order.

Why it matters: Improper deletion can corrupt the BST, causing incorrect search results.

Expert Zone

1

BST performance depends heavily on insertion order; random insertion tends to keep it balanced, but sorted insertion degrades it.

2

BSTs do not store duplicate values by default; handling duplicates requires special rules or data structures.

3

The height of a BST determines operation speed; balancing techniques are often layered on top to maintain efficiency.

When NOT to use

Avoid plain BSTs when data is mostly sorted or when guaranteed fast operations are needed; use balanced trees like AVL or Red-Black Trees, or hash tables for unordered fast lookups.

Production Patterns

BSTs are used in in-memory databases for ordered indexing, in language compilers for symbol tables, and in file systems for directory structures where order matters but balancing overhead is not justified.

Connections

Binary Search Algorithm

BST searching applies the same divide-and-conquer principle as binary search on sorted arrays.

Understanding binary search helps grasp why BSTs speed up searching by halving the search space at each step.

Balanced Trees (AVL, Red-Black Trees)

Balanced trees build on BSTs by adding rules to keep the tree height small and operations fast.

Knowing BST limitations clarifies why balancing is needed for consistent performance.

Library Book Organization

Both BSTs and library shelves organize items by order to speed up finding things.

Seeing BSTs as a method of organizing information like a library helps appreciate the importance of order in data structures.

Common Pitfalls

#1 Inserting nodes without following BST order.

Wrong approach:

Node* insert(Node* root, int val) {
if (!root) return new Node(val);
if (val > root->val) root->left = insert(root->left, val); // wrong side
else root->right = insert(root->right, val);
return root;
}

Correct approach:

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

Root cause:

Confusing the direction of insertion breaks BST ordering rules.

#2 Searching entire tree instead of using BST property.

Wrong approach:

bool search(Node* root, int val) {
if (!root) return false;
if (root->val == val) return true;
return search(root->left, val) || search(root->right, val); // checks both sides always
}

Correct approach:

bool search(Node* root, int val) {
if (!root) return false;
if (root->val == val) return true;
if (val < root->val) return search(root->left, val);
else return search(root->right, val);
}

Root cause:

Not using BST ordering wastes time by searching unnecessary branches.

#3 Deleting a node with two children incorrectly.

Wrong approach:

Node* deleteNode(Node* root, int val) {
if (!root) return nullptr;
if (val < root->val) root->left = deleteNode(root->left, val);
else if (val > root->val) root->right = deleteNode(root->right, val);
else {
delete root; // deletes without replacement
return nullptr;
}
return root;
}

Correct approach:

Node* deleteNode(Node* root, int val) {
if (!root) return nullptr;
if (val < root->val) root->left = deleteNode(root->left, val);
else if (val > root->val) root->right = deleteNode(root->right, val);
else {
if (!root->left) {
Node* temp = root->right;
delete root;
return temp;
} else if (!root->right) {
Node* temp = root->left;
delete root;
return temp;
} else {
Node* temp = findMin(root->right);
root->val = temp->val;
root->right = deleteNode(root->right, temp->val);
}
}
return root;
}

Root cause:

Ignoring the need to replace deleted nodes with two children breaks BST structure.

Key Takeaways

A Binary Search Tree organizes data so left children are smaller and right children are larger, enabling fast searching.

Plain binary trees lack order, making searching slow because every node might need checking.

BSTs speed up search, insertion, and deletion by guiding operations down one path instead of exploring all nodes.

BST efficiency depends on tree shape; unbalanced trees can degrade performance to linear time.

Balanced trees and other data structures build on BSTs to guarantee fast operations in all cases.

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