Why BST Over Plain Binary Tree in DSA Python - Performance Analysis

Time Complexity: Why BST Over Plain Binary Tree

O(log n) for balanced BST search, O(n) for plain binary tree search

Understanding Time Complexity

We want to understand why using a Binary Search Tree (BST) is faster than a plain binary tree for searching data.

How does the structure affect the time it takes to find something?

Scenario Under Consideration

Analyze the time complexity of searching for a value in these trees.

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

def search_plain(root, target):
    if root is None:
        return False
    if root.val == target:
        return True
    return search_plain(root.left, target) or search_plain(root.right, target)

def search_bst(root, target):
    if root is None:
        return False
    if root.val == target:
        return True
    elif target < root.val:
        return search_bst(root.left, target)
    else:
        return search_bst(root.right, target)
    

This code shows searching in a plain binary tree by checking all nodes, and in a BST by choosing left or right based on value.

Identify Repeating Operations

Look at what repeats when searching.

• Primary operation: Checking nodes one by one.
• How many times in plain tree: Could check every node (all n nodes).
• How many times in BST: Only follow one path down the tree (about log n nodes if balanced).

How Execution Grows With Input

As the number of nodes grows, how many checks do we do?

Input Size (n)	Plain Tree Checks	BST Checks (balanced)
10	Up to 10	About 4
100	Up to 100	About 7
1000	Up to 1000	About 10

Pattern observation: Plain tree search grows directly with n, but BST search grows slowly, roughly with the height of the tree.

Final Time Complexity

Time Complexity: O(n) for plain binary tree search, O(log n) for balanced BST search

This means searching in a plain tree can take time proportional to all nodes, but in a BST it takes much less time by skipping half the tree at each step.

Common Mistake

[X] Wrong: "BST search is always faster than plain tree search no matter what."

[OK] Correct: If the BST is not balanced, it can become like a plain tree, making search slow. The speed depends on tree shape.

Interview Connect

Knowing why BSTs help with faster searching shows you understand how data structure shapes affect speed. This skill helps you choose the right tool for the job in real coding tasks.

Self-Check

"What if the BST becomes unbalanced and looks like a linked list? How does that change the search time complexity?"

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