Why BST Over Plain Binary Tree in DSA Python - Quick Recap

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A Binary Search Tree is a special type of binary tree where each node's left child contains values less than the node, and the right child contains values greater than the node. This property helps in faster searching.

beginner

Why is searching faster in a BST compared to a plain binary tree?

Because BST keeps nodes in a sorted order, it allows us to decide whether to go left or right at each step, reducing the search space by half each time, unlike a plain binary tree where we might have to check every node.

beginner

What is the main disadvantage of a plain binary tree for searching?

A plain binary tree has no order, so to find a value, you might need to check every node, which can take a long time especially if the tree is large.

intermediate

How does the BST property help in insertion and deletion?

The BST property keeps the tree ordered, so when inserting or deleting, we know exactly where to go or what to adjust, making these operations efficient compared to a plain binary tree.

beginner

Can a plain binary tree be used for efficient searching?

No, because it lacks the ordering property of BST, searching in a plain binary tree is generally slower and less efficient.

What property makes BST faster for searching than a plain binary tree?

A Nodes are arranged in sorted order

B Nodes have only two children

C Nodes store extra data

D Nodes are connected randomly

BST nodes are arranged so left child < parent < right child, enabling faster search.

In a plain binary tree, how many nodes might you need to check to find a value?

A Only one

B Half of the nodes

C All nodes in worst case

D None

Without order, you might need to check every node to find a value.

Which operation benefits from BST's ordering property?

A Searching

B All of the above

C Deletion

D Insertion

BST's order helps searching, inserting, and deleting efficiently.

What happens if a BST becomes unbalanced?

A Search becomes slower

B Search becomes faster

C Tree becomes a plain binary tree

D Tree deletes itself

An unbalanced BST can degrade search speed closer to plain binary tree.

Which tree type is best for quick search in sorted data?

A Plain binary tree

B Graph

C Linked list

D Binary Search Tree

BST is designed for quick search in sorted data.

Explain why a Binary Search Tree is preferred over a plain binary tree for searching.

Think about how the order helps reduce the search steps.

Describe how the BST property affects insertion and deletion operations compared to a plain binary tree.

Consider how knowing where to go helps in these operations.

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