Why BST Over Plain Binary Tree in DSA Python - Why This Pattern

Mental Model

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

Analogy: Imagine a library where books are randomly placed on shelves (plain binary tree) versus a library where books are sorted by title (BST). Finding a book is much faster in the sorted library.

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

BST:
    7
   / \
  3   9
 /     / \
1     8  10

Dry Run Walkthrough

Input: Tree with nodes 7, 3, 9, 1, 8, 10 inserted in that order

Goal: Show how searching for 8 differs in a plain binary tree vs a BST

Step 1: Search for 8 in plain binary tree starting at root 7

Plain Tree: 7 [search=8]
BST: 7 [search=8]

Why: Start at root for both trees

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

Plain Tree: 7 -> 3 -> 9 [search=8]
BST: 7 [search=8]

Why: Plain tree has no order, so we must check multiple nodes

Step 3: In plain tree, check 1 (not 8), then 8 (found 8)

Plain Tree: 7 -> 3 -> 9 -> 1 -> 8 [found]
BST: 7 [search=8]

Why: Must explore multiple branches to find 8

Step 4: In BST, compare 8 with 7, go right to 9

BST: 7 -> 9 [search=8]

Why: BST property guides search direction

Step 5: Compare 8 with 9, go left to 8 (found 8)

BST: 7 -> 9 -> 8 [found]

Why: BST allows skipping unnecessary nodes

Result:

Plain Tree search path: 7 -> 3 -> 9 -> 1 -> 8 found
BST search path: 7 -> 9 -> 8 found
BST search is faster and more direct

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class PlainBinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = Node(val)
            return
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            if not node.left:
                node.left = Node(val)
                return
            else:
                queue.append(node.left)
            if not node.right:
                node.right = Node(val)
                return
            else:
                queue.append(node.right)

    def search(self, val):
        if not self.root:
            return False
        queue = [self.root]
        path = []
        while queue:
            node = queue.pop(0)
            path.append(str(node.val))
            if node.val == val:
                print("Plain Tree search path: " + " -> ".join(path) + " found")
                return True
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        print("Plain Tree search path: " + " -> ".join(path) + " not found")
        return False

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = Node(val)
            return
        curr = self.root
        while True:
            if val < curr.val:
                if curr.left:
                    curr = curr.left
                else:
                    curr.left = Node(val)
                    return
            else:
                if curr.right:
                    curr = curr.right
                else:
                    curr.right = Node(val)
                    return

    def search(self, val):
        curr = self.root
        path = []
        while curr:
            path.append(str(curr.val))
            if curr.val == val:
                print("BST search path: " + " -> ".join(path) + " found")
                return True
            elif val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        print("BST search path: " + " -> ".join(path) + " not found")
        return False

# Driver code
values = [7, 3, 9, 1, 8, 10]
plain_tree = PlainBinaryTree()
bst = BST()
for v in values:
    plain_tree.insert(v)
    bst.insert(v)

plain_tree.search(8)
bst.search(8)

queue = [self.root]

start level order traversal for plain tree insertion and search

node = queue.pop(0)

visit next node in plain tree

if not node.left: node.left = Node(val); return

insert new node at first empty left child in plain tree

if not node.right: node.right = Node(val); return

insert new node at first empty right child in plain tree

curr = self.root

start at root for BST insertion and search

if val < curr.val: curr = curr.left else curr = curr.right

move left or right in BST based on value comparison

if curr.val == val: return True

found target value in BST or plain tree

Output

Plain Tree search path: 7 -> 3 -> 9 -> 1 -> 8 found

BST search path: 7 -> 9 -> 8 found

Complexity Analysis

Time: O(n) for plain binary tree search because it may check all nodes; O(log n) average for BST search because it skips half the tree each step

Space: O(n) for both due to storing nodes; O(n) extra for queue in plain tree search

vs Alternative: BST is faster than plain binary tree for search because it keeps nodes ordered, reducing search steps from linear to logarithmic on average

Edge Cases

Empty tree

Search returns not found immediately

DSA Python

if not self.root: return False

Single node tree

Search compares root only and returns result

DSA Python

if curr.val == val: return True

Value not present

Search traverses all possible nodes and returns not found

DSA Python

while curr: ... return False

When to Use This Pattern

When you need fast search, insert, or delete in a tree structure, reach for BST because it keeps data ordered to speed up these operations.

Common Mistakes

Mistake: Treating plain binary tree as if it has order and trying to do binary search
Fix: Remember plain binary tree has no order; must check nodes one by one

Mistake: Not following BST property when inserting nodes
Fix: Always insert smaller values to left, larger or equal to right

Summary

BST keeps data ordered to allow faster search than plain binary tree.

Use BST when you want efficient search, insert, and delete in a tree.

The key insight is that ordering nodes lets you skip half the tree each step.

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 a 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 any pointers or links

Solution

1. Step 1: Understand the structure of BST vs Binary Tree

   A BST stores elements so that left child is smaller and right child is larger, maintaining sorted order. A plain Binary Tree has no such order.

2. Step 2: Analyze search efficiency

   Because of sorted order, BST allows searching by comparing and moving left or right, reducing search time to O(log n) on average, unlike plain Binary Tree which may require O(n).

3. Final Answer:

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

4. Quick Check:

   BST sorted order = faster search [OK]

Hint: BST keeps data sorted for quick searching [OK]

Common Mistakes:

• Thinking BST uses less memory
• Confusing number of children in BST
• Believing BST has no pointers

2. Which of the following is the correct way to check if a node's value is less than the root's value in a BST in Python?

easy

A. if node.value < root.value:

B. if node.value > root.value:

C. if node.value == root.value:

D. if node.value != root.value:

Solution

1. Step 1: Understand BST property for left subtree

   In BST, all nodes in the left subtree have values less than the root's value.

2. Step 2: Write condition to check left subtree

   To check if a node belongs to left subtree, compare if node.value is less than root.value using 'if node.value < root.value:'.

3. Final Answer:

   if node.value < root.value: -> Option A

4. Quick Check:

   Left subtree nodes < root [OK]

Hint: Left subtree nodes are less than root value [OK]

Common Mistakes:

• Using > instead of < for left subtree
• Checking equality instead of less than
• Using != which is unrelated

3. What will be the output of the following code snippet?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

root = None
for v in [10, 5, 15, 3]:
    root = insert(root, v)

print(root.left.left.val)

medium

A. 5

B. AttributeError

C. 10

D. 3

Solution

1. Step 1: Insert values into BST step-by-step

   Insert 10 as root. Insert 5 to left of 10. Insert 15 to right of 10. Insert 3 to left of 5.

2. Step 2: Trace root.left.left value

   root.left is node with value 5, root.left.left is node with value 3. So print(root.left.left.val) outputs 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Left child of 5 is 3 [OK]

Hint: Trace insertions stepwise to find node values [OK]

Common Mistakes:

• Confusing left and right child positions
• Assuming root.left.left is None
• Expecting root value instead of child

4. Find the error in the following BST insertion code:

def insert(root, val):
    if root is None:
        return Node(val)
    if val <= root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

medium

A. Should compare val > root.val instead of <= for left subtree

B. Missing return statement after recursive calls

C. Using <= allows duplicates on left, which may break BST uniqueness

D. Node class is not defined

Solution

1. Step 1: Analyze the comparison operator in insertion

   The code uses 'val <= root.val' to decide left subtree insertion, allowing duplicates on left side.

2. Step 2: Understand BST uniqueness property

   BST usually does not allow duplicates or places them consistently. Allowing duplicates on left can break balanced search assumptions.

3. Final Answer:

   Using <= allows duplicates on left, which may break BST uniqueness -> Option C

4. Quick Check:

   Duplicates on left break BST rules [OK]

Hint: Avoid <= to keep BST unique and balanced [OK]

Common Mistakes:

• Ignoring duplicate handling
• Thinking missing return causes error here
• Assuming Node class missing without context

5. You have a plain Binary Tree and want to improve search efficiency. Which approach best uses BST properties to achieve this?

1. Convert the plain Binary Tree into a BST by rearranging nodes.
2. Keep the tree structure but add a hash map for quick lookup.
3. Use BFS traversal every time to find nodes.
4. Store nodes in a list and search linearly.

hard

A. Store nodes in a list and search linearly

B. Convert the plain Binary Tree into a BST by rearranging nodes

C. Use BFS traversal every time to find nodes

D. Keep the tree structure but add a hash map for quick lookup

Solution

1. Step 1: Understand the goal to improve search efficiency

   Plain Binary Tree has no order, so search is slow (O(n)). BST property allows faster search (O(log n) average).

2. Step 2: Evaluate options for improving search

   Rearranging nodes to form BST uses sorted order property for efficient search. Other options either add extra space or do not improve search time.

3. Final Answer:

   Convert the plain Binary Tree into a BST by rearranging nodes -> Option B

4. Quick Check:

   BST structure = faster search [OK]

Hint: Rearrange tree to BST for efficient searching [OK]

Common Mistakes:

• Thinking hash map is part of BST
• Using BFS does not improve search time
• Linear search is slow and inefficient