Why BST Over Plain Binary Tree in DSA Python - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a value into a Binary Search Tree (BST).

DSA Python

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

Drag options to blanks, or click blank then click option'

Aroot.left

Broot.val

CNone

Dval

Attempts:

3 left

💡 Hint

Common Mistakes

Using root.val instead of val causes incorrect insertion.

Passing None breaks recursion.

The value to insert is passed recursively to the left subtree when it is less than the current node's value.

2fill in blank

medium

Complete the code to search for a value in a BST.

DSA Python

def search(root, val):
    if root is None or root.val == [1]:
        return root
    if val < root.val:
        return search(root.left, val)
    else:
        return search(root.right, val)

Drag options to blanks, or click blank then click option'

ANone

Broot.val

Cval

Droot.left

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with root.val instead of val causes wrong condition.

Using None instead of val breaks search logic.

We compare the node's value with the value we are searching for.

3fill in blank

hard

Fix the error in the code to find the minimum value node in a BST.

DSA Python

def minValueNode(node):
    current = node
    while current.[1] is not None:
        current = current.left
    return current

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cval

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using right instead of left leads to maximum value.

Using val or parent causes attribute errors.

The minimum value in a BST is found by going as far left as possible.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps node values to their depths in a BST.

DSA Python

depths = {node.val: [1] for node in nodes if node.val [2] 10 }

Drag options to blanks, or click blank then click option'

Anode.depth

Bnode.val

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.val for both key and value loses depth info.

Using > instead of < changes the filter condition.

We map each node's value to its depth, filtering nodes with values less than 10.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps uppercase node values to their depths if depth is greater than 2.

DSA Python

result = { [1]: [2] for node in nodes if node.depth [3] 2 }

Drag options to blanks, or click blank then click option'

Anode.val.upper()

Bnode.depth

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.val instead of uppercase.

Using < instead of > changes filter logic.

The keys are uppercase node values, values are depths, filtered by depth greater than 2.

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