BST Find Maximum Element in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find maximum element in a BST

What is the output of the following code that finds the maximum element in a Binary Search Tree (BST)?

DSA Python

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

def find_max(root):
    current = root
    while current.right:
        current = current.right
    return current.val

# Construct BST
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.right.right = Node(20)
root.right.left = Node(12)

print(find_max(root))

A 20

B 15

C 12

D 10

💡 Hint

In a BST, the maximum element is the rightmost node.

The function moves to the right child repeatedly until it reaches the rightmost node, which holds the maximum value 20.

❓ Predict Output

intermediate

Output of find_max with single node BST

What will be printed when find_max is called on a BST with only one node?

DSA Python

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

def find_max(root):
    current = root
    while current.right:
        current = current.right
    return current.val

root = Node(42)
print(find_max(root))

A 42

B None

C 0

D Error

💡 Hint

If there is no right child, the root itself is the maximum.

Since the BST has only one node with value 42 and no right child, the function returns 42.

🔧 Debug

advanced

Identify the error in find_max function

What error will this code raise when trying to find the maximum element in a BST?

DSA Python

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

def find_max(root):
    current = root
    while current.right is not None:
        current = current.right
    return current.val

root = Node(10)
root.right = Node(20)
print(find_max(root))

A AttributeError

B Returns 10

C Infinite loop

D Returns 20

💡 Hint

Check the direction of traversal inside the loop.

The original code incorrectly moved left inside the loop. The corrected code moves right until no right child exists, returning 20.

🧠 Conceptual

advanced

Maximum element in an empty BST

What happens if you call find_max on an empty BST (root is None)?

DSA Python

def find_max(root):
    current = root
    while current.right:
        current = current.right
    return current.val

print(find_max(None))

A Returns None

B AttributeError: 'NoneType' object has no attribute 'right'

C Returns 0

D SyntaxError

💡 Hint

Consider what happens when current is None and you try to access current.right.

Since root is None, current is None, and accessing current.right raises AttributeError.

🚀 Application

expert

Find maximum element in BST with parent pointers

Given a BST node class with parent pointers, which code snippet correctly finds the maximum element starting from any node in the tree?

DSA Python

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

# Assume 'node' is any node in the BST

A

def find_max(node):
    while node.parent:
        node = node.parent
    return node.val

B

def find_max(node):
    while node.left:
        node = node.left
    return node.val

C

def find_max(node):
    while node.right:
        node = node.right
    return node.val

D

def find_max(node):
    while node.parent and node.parent.right == node:
        node = node.parent
    return node.val

💡 Hint

Maximum element is the rightmost node in the BST subtree rooted at the given node.

To find maximum from any node, move right until no right child exists. Parent pointers are not needed for this operation.

Practice

1. In a Binary Search Tree (BST), where is the maximum element always located?

easy

A. At the root node

B. At the leftmost node

C. At the rightmost node

D. At any leaf node

Solution

1. Step 1: Understand BST property

   In a BST, all values in the right subtree are greater than the root, so the largest value is towards the right.

2. Step 2: Locate the maximum element

   The maximum element is found by moving to the right child repeatedly until no more right child exists.

3. Final Answer:

   At the rightmost node -> Option C

4. Quick Check:

   Maximum element = rightmost node [OK]

Hint: Go right until no more right child [OK]

Common Mistakes:

• Thinking maximum is at the root
• Looking at left subtree for maximum
• Assuming maximum can be any leaf

2. Which of the following Python code snippets correctly finds the maximum element in a BST node structure where each node has left and right attributes?

easy

A. def find_max(root):
while root.right:
root = root.right
return root.data

B. def find_max(root):
while root.left:
root = root.left
return root.data

C. def find_max(root):
if root is None:
return None
return root.data

D. def find_max(root):
return max(root.left.data, root.right.data)

Solution

1. Step 1: Check traversal direction for max

   Maximum is found by moving right until no right child exists, so loop should check root.right.

2. Step 2: Verify code correctness

   def find_max(root): while root.right: root = root.right return root.data correctly loops while root.right exists, then returns root.data. Others either go left or incorrectly use max function.

3. Final Answer:

   while root.right: root = root.right; return root.data -> Option A

4. Quick Check:

   Loop right child until none = correct max finder [OK]

Hint: Loop on root.right to find max [OK]

Common Mistakes:

• Looping on root.left instead of root.right
• Returning root.data without traversal
• Using max() on children without recursion

3. What will be the output of the following code snippet?

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

def find_max(root):
    current = root
    while current.right:
        current = current.right
    return current.data

root = Node(10)
root.left = Node(5)
root.right = Node(20)
root.right.right = Node(30)
print(find_max(root))

medium

A. 10

B. 30

C. 20

D. 5

Solution

1. Step 1: Trace the BST structure

   Root is 10, right child 20, right of 20 is 30. Maximum is the rightmost node 30.

2. Step 2: Follow the find_max function

   Function moves right from 10 to 20, then to 30, then stops as 30 has no right child, returning 30.

3. Final Answer:

   30 -> Option B

4. Quick Check:

   Rightmost node data = 30 [OK]

Hint: Follow right pointers to last node [OK]

Common Mistakes:

• Returning root data instead of rightmost
• Confusing left and right children
• Stopping traversal too early

4. The following code is intended to find the maximum element in a BST but contains a bug. What is the bug?

def find_max(root):
    if root is None:
        return None
    while root.left:
        root = root.left
    return root.data

medium

A. It causes infinite loop

B. It does not handle empty tree

C. It returns None instead of data

D. It incorrectly traverses left child instead of right child

Solution

1. Step 1: Analyze traversal direction

   The code loops while root.left exists, moving left, but maximum is on the right side in BST.

2. Step 2: Identify correct traversal

   To find maximum, loop should be on root.right until no right child remains.

3. Final Answer:

   It incorrectly traverses left child instead of right child -> Option D

4. Quick Check:

   Max element found by going right, not left [OK]

Hint: Max is rightmost, so loop on root.right [OK]

Common Mistakes:

• Looping on left child for max
• Ignoring empty tree check
• Returning wrong node data

5. Given a BST where some nodes have duplicate values, which approach correctly finds the maximum element considering duplicates are allowed only on the right subtree?

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

def find_max(root):
    # Your code here
    pass

Choose the correct implementation to find the maximum element.

hard

A. def find_max(root):
current = root
while current.right:
current = current.right
return current.data

B. def find_max(root):
if root.right is None:
return root.data
return find_max(root.left)

C. def find_max(root):
max_val = root.data
max_val = max(max_val, find_max(root.left))
max_val = max(max_val, find_max(root.right))
return max_val

D. def find_max(root):
if root is None:
return float('-inf')
return max(root.data, find_max(root.left))

Solution

1. Step 1: Understand duplicates in BST

   Duplicates allowed only on right means maximum is still the rightmost node.

2. Step 2: Choose correct traversal

   def find_max(root): current = root while current.right: current = current.right return current.data correctly moves right until no right child exists, returning the maximum value.

3. Step 3: Analyze other options

   def find_max(root): if root.right is None: return root.data return find_max(root.left) incorrectly recurses left; def find_max(root): max_val = root.data max_val = max(max_val, find_max(root.left)) max_val = max(max_val, find_max(root.right)) return max_val lacks None checks before recursing, causing AttributeError on None children; def find_max(root): if root is None: return float('-inf') return max(root.data, find_max(root.left)) ignores right subtree.

4. Final Answer:

   while current.right: current = current.right; return current.data -> Option A

5. Quick Check:

   Rightmost node = max even with duplicates [OK]

Hint: Duplicates on right? Still go rightmost [OK]

Common Mistakes:

• Searching left subtree for max
• Checking both subtrees unnecessarily
• Ignoring None checks causing errors