BST Property and Why It Matters in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on a BST

What is the output of the inorder traversal of this BST after inserting the values 10, 5, 15, 3, 7, 12, 18 in that order?

DSA Python

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

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

root = None
for v in [10, 5, 15, 3, 7, 12, 18]:
    root = insert(root, v)
print(inorder(root))

A [3, 5, 7, 10, 12, 15, 18]

B [10, 5, 3, 7, 15, 12, 18]

C [18, 15, 12, 10, 7, 5, 3]

D [5, 3, 7, 10, 12, 15, 18]

💡 Hint

Inorder traversal of a BST visits nodes in ascending order.

Inorder traversal visits left subtree, then root, then right subtree. For BST, this produces sorted values.

🧠 Conceptual

intermediate

Why Does BST Property Matter for Search?

Why is the BST property important for efficient searching in a binary search tree?

A It ensures all nodes have two children, making the tree balanced.

B It allows skipping half of the tree at each step, reducing search time to O(log n) on average.

C It stores values in a linked list fashion for sequential access.

D It guarantees the tree is always perfectly balanced.

💡 Hint

Think about how the tree structure helps find values faster than checking every node.

The BST property lets us decide to go left or right at each node, skipping half the nodes on average, leading to O(log n) search time.

🔧 Debug

advanced

Identify the Bug in BST Insertion

What error will this BST insertion code cause when inserting duplicate values?

DSA Python

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)
    elif val > root.val:
        root.right = insert(root.right, val)
    # No else case for val == root.val
    return root

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

A Duplicates are inserted to the right subtree causing imbalance.

B Duplicates cause infinite recursion leading to a RecursionError.

C Duplicates are ignored; the tree remains unchanged for duplicate insertions.

D Duplicates are inserted to the left subtree causing imbalance.

💡 Hint

Check what happens when val equals root.val in the insert function.

Since no action is taken when val == root.val, duplicates are ignored and not inserted.

❓ Predict Output

advanced

Output After Deleting a Node in BST

What is the inorder traversal output after deleting the node with value 10 from this BST?

DSA Python

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

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

def find_min(root):
    while root.left:
        root = root.left
    return root

def delete(root, val):
    if root is None:
        return root
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = find_min(root.right)
        root.val = temp.val
        root.right = delete(root.right, temp.val)
    return root

root = None
for v in [10, 5, 15, 3, 7, 12, 18]:
    root = insert(root, v)
root = delete(root, 10)
print(inorder(root))

A [3, 5, 7, 12, 15, 18]

B [3, 5, 7, 10, 12, 15, 18]

C [3, 5, 7, 15, 12, 18]

D [5, 7, 12, 15, 18]

💡 Hint

When deleting a node with two children, replace it with the smallest value in the right subtree.

Deleting 10 replaces it with 12 (smallest in right subtree), then deletes 12 from right subtree. Inorder traversal reflects this.

🧠 Conceptual

expert

Why BST Property is Crucial for Balanced Trees

Which statement best explains why maintaining the BST property is crucial when balancing a binary search tree?

A The BST property guarantees the tree height is always minimal without rotations.

B The BST property allows storing duplicate values in any subtree without restrictions.

C Balancing a tree does not require the BST property as long as the tree is complete.

D Maintaining the BST property ensures that after rotations, the tree remains a valid search tree with ordered nodes.

💡 Hint

Think about what happens to node order after tree rotations.

Rotations used in balancing must keep the BST property intact so the tree remains correctly ordered for searching.

Practice

1. What is the main property that defines a Binary Search Tree (BST)?

easy

A. Left child nodes are smaller, right child nodes are larger than the parent node

B. All nodes have exactly two children

C. Nodes are arranged in level order

D. Each node has a pointer to its parent only

Solution

1. Step 1: Understand BST node arrangement

   In a BST, for each node, all nodes in the left subtree have smaller values and all nodes in the right subtree have larger values.

2. Step 2: Compare options with BST definition

   Left child nodes are smaller, right child nodes are larger than the parent node correctly states this property. Other options describe different tree types or incorrect properties.

3. Final Answer:

   Left child nodes are smaller, right child nodes are larger than the parent node -> Option A

4. Quick Check:

   BST property = Left smaller, right larger [OK]

Hint: Remember BST means left < node < right [OK]

Common Mistakes:

• Confusing BST with complete binary tree
• Thinking all nodes must have two children
• Assuming nodes are sorted by level

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

easy

A. if node.left.value > node.value:

B. if node.left > node.value:

C. if node.left.value == node.value:

D. if node.left.value < node.value:

Solution

1. Step 1: Understand node attribute access

   In Python, to access the left child's value, use node.left.value.

2. Step 2: Compare values for BST property

   We check if left child's value is less than the node's value, so the condition is node.left.value < node.value.

3. Final Answer:

   if node.left.value < node.value: -> Option D

4. Quick Check:

   Left child value < node value syntax [OK]

Hint: Use node.left.value to access left child's value [OK]

Common Mistakes:

• Comparing node.left directly without .value
• Using > instead of < for left child
• Using == which is incorrect for BST property

3. Consider the following Python code that inserts values into a BST:

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, 7]:
    root = insert(root, v)

print(root.left.right.val)

What is the output?

medium

A. 5

B. 7

C. 3

D. 15

Solution

1. Step 1: Trace insertion order and BST structure

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

2. Step 2: Identify root.left.right node value

   root.left is node with value 5; root.left.right is node with value 7.

3. Final Answer:

   7 -> Option B

4. Quick Check:

   root.left.right.val = 7 [OK]

Hint: Draw tree nodes to find left-right child quickly [OK]

Common Mistakes:

• Confusing left and right child positions
• Assuming insertion order is different
• Printing root.left.val instead of root.left.right.val

4. The following code attempts to check if a binary tree is a BST but has a bug:

def is_bst(node, min_val=float('-inf'), max_val=float('inf')):
    if node is None:
        return True
    if node.val < min_val or node.val > max_val:
        return False
    return is_bst(node.left, min_val, node.val) and is_bst(node.right, node.val, max_val)

What is the bug in this code?

medium

A. The function does not check for duplicate values properly

B. The base case should return false instead of true

C. The recursive calls swap min_val and max_val incorrectly

D. The comparison should use <= and >= instead of < and >

Solution

1. Step 1: Analyze BST validation logic

   The code checks if node.val is between min_val and max_val, then recursively checks left and right subtrees with updated ranges.

2. Step 2: Identify handling of duplicates

   Using < and > allows duplicates equal to node.val on both sides, which violates BST property if duplicates are not allowed or must be on one side only.

3. Final Answer:

   The function does not check for duplicate values properly -> Option A

4. Quick Check:

   Duplicates need special handling in BST checks [OK]

Hint: Check how duplicates are handled in BST validation [OK]

Common Mistakes:

• Changing base case return value incorrectly
• Swapping min_val and max_val in recursive calls
• Ignoring duplicate value rules in BST

5. You have a BST where each node stores an integer. You want to find the kth smallest element efficiently. Which property of BST helps achieve this, and what is the best approach?

hard

A. BST property doesn't help; convert BST to list and sort it to find kth element

B. BST's pre-order traversal gives sorted order; perform pre-order traversal and stop at kth element

C. BST's in-order traversal gives sorted order; perform in-order traversal and stop at kth element

D. BST's post-order traversal gives sorted order; perform post-order traversal and stop at kth element

Solution

1. Step 1: Recall BST traversal properties

   In-order traversal of BST visits nodes in ascending sorted order.

2. Step 2: Use in-order traversal to find kth smallest

   Perform in-order traversal and count nodes visited; stop when count reaches k to get kth smallest element efficiently.

3. Final Answer:

   BST's in-order traversal gives sorted order; perform in-order traversal and stop at kth element -> Option C

4. Quick Check:

   In-order traversal = sorted nodes [OK]

Hint: Use in-order traversal to get sorted nodes in BST [OK]

Common Mistakes:

• Using pre-order or post-order which are not sorted
• Sorting after converting BST to list wastes time
• Ignoring BST property for efficient search