BST Find Maximum Element in DSA C++ - Execution Trace

Concept Flow - BST Find Maximum Element

Start at root node

↓

Check if right child exists?

No→Current node is max

Yes↓

Move to right child

↩Back to check right child

Start at the root and keep moving to the right child until there is no right child left. The last node visited is the maximum.

Execution Sample

DSA C++

Node* findMax(Node* root) {
  if (!root) return nullptr;
  while (root->right) {
    root = root->right;
  }
  return root;
}

This code finds the maximum element in a BST by moving right until no right child exists.

Execution Table

Step	Operation	Current Node	Right Child Exists?	Pointer Changes	Visual State
1	Start at root	50	Yes	current = 50	50 -> 30, 70
2	Move right	70	Yes	current = 70	50 -> 30, 70 -> 60, 80
3	Move right	80	No	current = 80	50 -> 30, 70 -> 60, 80
4	Return current as max	80	No	return 80	Max element found: 80

💡 No right child at node 80, so 80 is the maximum element.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
current	root (50)	50	70	80	80

Key Moments - 3 Insights

Why do we keep moving to the right child to find the maximum?

In a BST, all right children have values greater than their parent. So moving right leads to larger values. See execution_table steps 1 to 3 where current moves right.

What if the tree is empty (root is null)?

The function returns nullptr immediately (step 1 in code). No nodes to check means no maximum.

Why do we stop when there is no right child?

Because the node without a right child is the largest in that path. Execution_table step 3 shows current at 80 with no right child, so we stop.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node at step 2?

A 70

B 50

C 80

D 30

💡 Hint

Check the 'Current Node' column at step 2 in execution_table.

At which step does the condition 'Right Child Exists?' become No?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Right Child Exists?' column in execution_table.

If the root node had no right child, what would be the maximum element?

A The left child of root

B The root node itself

C Null (no max)

D The right child of root

💡 Hint

Refer to the concept_flow and execution_table step 1 where no right child means current node is max.

Concept Snapshot

BST Find Maximum Element:
- Start at root node
- Move right while right child exists
- Stop when no right child
- Current node is maximum
- Returns pointer to max node

Full Transcript

To find the maximum element in a Binary Search Tree (BST), start at the root node. Check if the current node has a right child. If yes, move to the right child and repeat. If no right child exists, the current node is the maximum. This works because in BSTs, right children always have greater values than their parents. If the tree is empty, return null. The code uses a loop to move right until no right child is found, then returns that node as maximum.

Practice

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

easy

A. At the leftmost node

B. At any leaf node

C. At the root node

D. At the rightmost node

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes have smaller values and right child nodes have larger values than their parent.

2. Step 2: Locate maximum element

   The maximum element is the rightmost node because it has no right child and is greater than all other nodes.

3. Final Answer:

   At the rightmost node -> Option D

4. Quick Check:

   Maximum = rightmost node [OK]

Hint: Maximum is always the rightmost node in BST [OK]

Common Mistakes:

• Confusing maximum with root node
• Thinking maximum is at leftmost node
• Assuming maximum can be any leaf

2. Which of the following C++ function signatures correctly finds the maximum element in a BST node pointer root?

easy

A. int findMax(Node* root) { return root->data; }

B. int findMax(Node* root) { while(root->left) root = root->left; return root->data; }

C. int findMax(Node* root) { while(root->right) root = root->right; return root->data; }

D. int findMax(Node* root) { while(root->parent) root = root->parent; return root->data; }

Solution

1. Step 1: Check traversal direction for maximum

   Maximum is found by moving right until no right child exists.

2. Step 2: Verify code correctness

   int findMax(Node* root) { while(root->right) root = root->right; return root->data; } correctly loops while root->right exists and returns root->data.

3. Final Answer:

   int findMax(Node* root) { while(root->right) root = root->right; return root->data; } -> Option C

4. Quick Check:

   Traverse right child to find max [OK]

Hint: Traverse right child pointer until null [OK]

Common Mistakes:

• Traversing left child instead of right
• Returning root data without traversal
• Using parent pointer which may not exist

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

struct Node {
  int data;
  Node* left;
  Node* right;
};

Node* root = new Node{10, nullptr, nullptr};
root->right = new Node{20, nullptr, nullptr};
root->right->right = new Node{30, nullptr, nullptr};

int findMax(Node* root) {
  while(root->right) root = root->right;
  return root->data;
}

std::cout << findMax(root) << std::endl;

medium

A. 30

B. 20

C. 10

D. Runtime error

Solution

1. Step 1: Trace the BST structure

   Root is 10, right child 20, right child's right child 30.

2. Step 2: Follow findMax function

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

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Rightmost node data = 30 [OK]

Hint: Rightmost node data is maximum [OK]

Common Mistakes:

• Returning root data without traversal
• Confusing left and right pointers
• Assuming runtime error due to nullptr

4. Identify the bug in the following C++ function to find the maximum element in a BST:

int findMax(Node* root) {
  if (root == nullptr) return -1;
  while(root->left) {
    root = root->left;
  }
  return root->data;
}

medium

A. Should traverse right child, not left child

B. Should return 0 instead of -1 for nullptr

C. Missing check for root->right in while loop

D. Function should be void, not int

Solution

1. Step 1: Analyze traversal direction

   The function incorrectly traverses left child to find maximum, but maximum is at rightmost node.

2. Step 2: Correct traversal logic

   Change while(root->left) to while(root->right) to find maximum correctly.

3. Final Answer:

   Should traverse right child, not left child -> Option A

4. Quick Check:

   Maximum = rightmost node, not leftmost [OK]

Hint: Maximum is rightmost, so traverse right pointer [OK]

Common Mistakes:

• Traversing left child instead of right
• Ignoring nullptr check
• Returning wrong default value

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

struct Node {
  int data;
  Node* left;
  Node* right;
};

// Function to find max element
int findMax(Node* root) {
  // Your code here
}

hard

A. Traverse right while root->right exists and root->right->data > root->data

B. Traverse right while root->right exists only

C. Traverse left while root->left exists and root->left->data > root->data

D. Return root->data without traversal

Solution

1. Step 1: Understand duplicates in BST

   Even with duplicates allowed on the right subtree, BST property ensures right subtree values are >= parent, so maximum is always the rightmost node.

2. Step 2: Correct traversal for maximum

   Traverse right while root->right exists only. No data comparison needed due to BST invariants.

3. Final Answer:

   Traverse right while root->right exists only -> Option B

4. Quick Check:

   Traverse right child pointer until null [OK]

Hint: Traverse right child pointer until null [OK]

Common Mistakes:

• Using strict > check which stops early on duplicates
• Traversing left instead of right
• Returning root data without traversal