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 from the root and keep moving to the right child until there is no right child left. The last node visited is the maximum element.

Execution Sample

DSA C

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

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

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	root -> 50	50 / \ 30 70 / \ / \ 20 40 60 80
2	Move to right child	70	Yes	root -> 70	50 / \ 30 70 / \ / \ 20 40 60 80
3	Move to right child	80	No	root -> 80	50 / \ 30 70 / \ / \ 20 40 60 80
4	No right child, max found	80	No	root stays 80	50 / \ 30 70 / \ / \ 20 40 60 80

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
root	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 values in the right subtree are greater than the current node. So moving right leads to larger values. See execution_table steps 1 to 3.

What if the tree has only one node?

If there is no right child at the root, the root itself is the maximum. This is shown in execution_table step 4 where no right child means max found.

Why do we stop when right child is NULL, not when current node is NULL?

We stop at the last valid node before NULL because NULL means no node exists. The last node visited is the maximum. See execution_table step 4.

Visual Quiz - 3 Questions

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

A 80

B 70

C 50

D 60

💡 Hint

Check the 'Current Node' column in execution_table row for step 3.

At which step does the algorithm find that there is no right child?

A Step 2

B Step 4

C Step 3

D Step 1

💡 Hint

Look at the 'Right Child Exists?' column and find where it says 'No' and max is found.

If the root node had no right child, how would the pointer changes differ?

A root would move to left child

B root would become NULL immediately

C root would stay at root node

D root would move to right child anyway

💡 Hint

Refer to key_moments about stopping when no right child exists.

Concept Snapshot

BST Find Maximum Element:
- Start at root node
- While right child exists, move right
- When no right child, current node is max
- Returns max node's data
- Works because BST right subtree has larger values

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, the current node is the maximum element. This works because in BSTs, right children always have greater values than their parents. The code uses a loop to move right until no right child exists, then returns that node's data. This method handles single-node trees by returning the root itself if no right child exists.

Practice

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

easy

A. At any leaf node

B. At the leftmost node

C. At the rightmost node

D. At the root 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 C

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 code snippets correctly finds the maximum element in a BST?

easy

A. while(root->left != NULL) root = root->left; return root->data;

B. while(root->right != NULL) root = root->right; return root->data;

C. if(root == NULL) return INT_MIN; return root->data;

D. return root->data;

Solution

1. Step 1: Analyze code logic

   while(root->right != NULL) root = root->right; return root->data; moves right until no right child exists, which is correct for max in BST.

2. Step 2: Check other options

   while(root->left != NULL) root = root->left; return root->data; moves left (minimum), C returns root data without traversal, D returns root data directly.

3. Final Answer:

   while(root->right != NULL) root = root->right; return root->data; -> Option B

4. Quick Check:

   Traverse rightmost node for max [OK]

Hint: Traverse right child until NULL to find max [OK]

Common Mistakes:

• Traversing left child instead of right
• Returning root data without traversal
• Not checking for NULL pointers

3. What will be the output of the following code snippet that finds the maximum element in a BST?

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

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

// BST structure:
//       10
//      /  \
//     5    20
//         /  \
//        15   30

int main() {
  // Assume BST is created as above
  printf("%d", findMax(root));
  return 0;
}

medium

A. 30

B. 20

C. 15

D. 10

Solution

1. Step 1: Understand BST structure

   The rightmost node is 30, which is the maximum element.

2. Step 2: Trace findMax function

   The function moves right from root (10) to 20, then to 30, stops as 30->right is NULL, returns 30.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Max element = 30 [OK]

Hint: Max is rightmost node: 10 -> 20 -> 30 [OK]

Common Mistakes:

• Returning root data without traversal
• Confusing max with root or left child
• Not following right pointers correctly

4. Identify the error in the following C function that is supposed to find the maximum element in a BST:

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

medium

A. It returns -1 for empty tree instead of INT_MIN

B. It should use recursion instead of loop

C. It does not check if root is NULL before accessing data

D. It traverses left instead of right to find maximum

Solution

1. Step 1: Analyze traversal direction

   The function moves left to find max, but max is at rightmost node in BST.

2. Step 2: Check other issues

   Returning -1 is acceptable for empty tree; checking root NULL is done; recursion is optional.

3. Final Answer:

   It traverses left instead of right to find maximum -> Option D

4. Quick Check:

   Max is rightmost, not leftmost [OK]

Hint: Max element is at rightmost, not leftmost node [OK]

Common Mistakes:

• Confusing left and right child traversal
• Ignoring NULL checks
• Thinking recursion is mandatory

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?

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

What is the output if the BST has nodes with values: 10, 20, 20, 30 (duplicates on right)?

hard

A. 30

B. 20

C. 10

D. Error due to duplicates

Solution

1. Step 1: Understand duplicates in BST

   Duplicates allowed on right means equal values go to right subtree, so max is still rightmost node.

2. Step 2: Trace findMax with duplicates

   Traversal moves right from 10 to 20, then to next 20, then to 30, which is rightmost and max.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Duplicates on right do not affect max = rightmost node [OK]

Hint: Duplicates on right subtree keep max at rightmost node [OK]

Common Mistakes:

• Assuming duplicates cause errors
• Stopping at first duplicate value
• Confusing duplicates location in BST