Why BST Over Plain Binary Tree in DSA Python - See It Work

Why BST Over Plain Binary Tree

📖 Scenario: Imagine you have a collection of books with unique ID numbers. You want to organize them so you can quickly find any book by its ID. You can arrange them in a simple tree or a special tree called a Binary Search Tree (BST).

🎯 Goal: Build two trees: a plain binary tree and a binary search tree (BST) with the same book IDs. Then, compare how quickly you can find a book in each tree.

📋 What You'll Learn

Create a plain binary tree with book IDs 10, 5, 15, 3, 7, 12, 18

Create a binary search tree (BST) with the same book IDs

Write a function to search for a book ID in both trees

Print the search result for book ID 7 in both trees

💡 Why This Matters

🌍 Real World

Organizing data like books, contacts, or products so you can find items quickly.

💼 Career

Understanding BSTs helps in software development roles that require efficient data storage and retrieval.

1

Create a plain binary tree with book IDs

Create a class called Node with attributes value, left, and right. Then create nodes for book IDs 10, 5, 15, 3, 7, 12, 18 and link them to form this plain binary tree structure:
10 is root, 5 is left child of 10, 15 is right child of 10, 3 is left child of 5, 7 is right child of 5, 12 is left child of 15, 18 is right child of 15.

DSA Python

# Define Node class and create plain binary tree nodes
# Your code here

Hint

Start by defining a simple Node class. Then create each node and connect them as described.

2

Create a binary search tree (BST) with the same book IDs

Create a function called insert_bst(root, value) that inserts a new value into the BST following BST rules (left child smaller, right child larger). Use it to insert book IDs 10, 5, 15, 3, 7, 12, 18 into root_bst.

DSA Python

def insert_bst(root, value):
    # Your code here

root_bst = None
# Insert values 10, 5, 15, 3, 7, 12, 18 into root_bst
# Your code here

Hint

Use recursion to insert nodes in the BST. Compare the value to decide left or right child.

3

Write a function to search for a book ID in both trees

Write a function called search_tree(root, target) that searches for target in any binary tree by checking nodes recursively. Then write a function called search_bst(root, target) that searches for target in a BST efficiently by comparing values and choosing left or right child.

DSA Python

def search_tree(root, target):
    # Your code here

def search_bst(root, target):
    # Your code here

Hint

For search_tree, check both left and right children. For search_bst, use the BST property to decide which side to search.

4

Print the search result for book ID 7 in both trees

Use print statements to show the result of searching for book ID 7 in root_plain using search_tree and in root_bst using search_bst. Print exactly these two lines:
"Found 7 in plain tree: True"
"Found 7 in BST: True"

DSA Python

# Print search results for book ID 7 in both trees
# Your code here

Hint

Use print with string concatenation or f-strings to show the search results exactly as given.

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