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 no right child exists. That node is the maximum.

Execution Sample

DSA C#

Node FindMax(Node root) {
  Node current = root;
  while (current.Right != null) {
    current = current.Right;
  }
  return current;
}

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 / \ 60 80
2	Check right child	50	Yes	Move current to 70	50 / \ 30 70 / \ 60 80
3	Check right child	70	Yes	Move current to 80	50 / \ 30 70 / \ 60 80
4	Check right child	80	No	Stop, current is max	50 / \ 30 70 / \ 60 80
5	Return max node	80	No	Return node 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	After Step 4	Final
current	null	50	70	80	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 2 and 3 where current moves right.

What if the tree has only one node?

If there is only one node, it has no right child. So the root itself is the maximum. This matches execution_table step 4 where no right child means stop.

Why do we stop when current.Right is null, not when current is null?

Stopping when current.Right is null means current is the largest node. If we moved until current is null, we would go past the largest node. See execution_table step 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 3?

A 50

B 70

C 80

D 60

💡 Hint

Check the 'Pointer Changes' and 'Current Node' columns at step 3.

At which step does the algorithm stop moving right because there is no right child?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look for the step where 'Right Child Exists?' is 'No' in the execution_table.

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

A The left child

B The root node itself

C Null

D The smallest element

💡 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
- Return current node
- Works because right child > parent in BST

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 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 is found, then returns that node. For example, starting at 50, we move right to 70, then to 80, which has no right child, so 80 is the maximum. If the tree has only one node, that node is the maximum. This method ensures we do not go past the largest node by stopping when current.Right is null.

Practice

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

easy

A. At the root node

B. At the rightmost node

C. At the leftmost node

D. At any leaf node

Solution

1. Step 1: Understand BST property

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

2. Step 2: Locate maximum element

   The maximum element is the largest value, so it must be the rightmost node because values increase to the right.

3. Final Answer:

   At the rightmost node -> Option B

4. Quick Check:

   Maximum element = rightmost node [OK]

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

Common Mistakes:

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

2. Which of the following C# code snippets correctly finds the maximum element in a BST node called root?

easy

A. while (root.Left != null) { root = root.Left; } return root.Value;

B. if (root.Left == null) return root.Value; else return root.Left.Value;

C. while (root.Right != null) { root = root.Right; } return root.Value;

D. return root.Value; // root is always max

Solution

1. Step 1: Check traversal direction

   To find max, traverse right child nodes until no more right child exists.

2. Step 2: Verify code correctness

   while (root.Right != null) { root = root.Right; } return root.Value; uses a while loop to move right until root.Right is null, then returns root.Value, which is correct.

3. Final Answer:

   while (root.Right != null) { root = root.Right; } return root.Value; -> Option C

4. Quick Check:

   Traverse right until null, then return value [OK]

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

Common Mistakes:

• Traversing left child instead of right
• Returning root value without traversal
• Using incorrect condition in loop

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

class Node {
  public int Value;
  public Node Left, Right;
  public Node(int val) { Value = val; Left = Right = null; }
}

Node root = new Node(10);
root.Left = new Node(5);
root.Right = new Node(15);
root.Right.Right = new Node(20);

Node current = root;
while (current.Right != null) {
  current = current.Right;
}
Console.WriteLine(current.Value);

medium

A. 5

B. 15

C. 10

D. 20

Solution

1. Step 1: Trace the BST structure

   Root is 10, right child 15, right child of 15 is 20. So rightmost node is 20.

2. Step 2: Follow the loop

   The loop moves current from 10 to 15, then to 20, then stops because 20.Right is null.

3. Final Answer:

   20 -> Option D

4. Quick Check:

   Rightmost node value = 20 [OK]

Hint: Rightmost node value is maximum [OK]

Common Mistakes:

• Stopping at 15 instead of 20
• Printing root value instead of max
• Confusing left and right children

4. The following C# method is intended to find the maximum element in a BST. What is the error?

int FindMax(Node root) {
  if (root == null) return int.MinValue;
  if (root.Right == null) return root.Value;
  return FindMax(root.Left);
}

medium

A. It should recurse on root.Right, not root.Left

B. It should return int.MaxValue when root is null

C. It should check root.Left instead of root.Right

D. No error, code is correct

Solution

1. Step 1: Analyze recursion direction

   To find max, recursion must go right, but code recurses left incorrectly.

2. Step 2: Identify correct recursion

   Change FindMax(root.Left) to FindMax(root.Right) to find max correctly.

3. Final Answer:

   It should recurse on root.Right, not root.Left -> Option A

4. Quick Check:

   Max found by right recursion [OK]

Hint: Max search recurses right child, not left [OK]

Common Mistakes:

• Recursing left child instead of right
• Returning wrong base case value
• Ignoring null root check

5. Given a BST where some nodes have duplicate values, which approach correctly finds the maximum value considering duplicates?

int FindMaxWithDuplicates(Node root) {
  if (root == null) return int.MinValue;
  int rightMax = FindMaxWithDuplicates(root.Right);
  return Math.Max(root.Value, rightMax);
}

What is the output of FindMaxWithDuplicates on this BST? Root: 10 Left: 5 Right: 10 Right.Right: 15 Right.Right.Right: 15

hard

A. 15

B. 10

C. 5

D. Error due to duplicates

Solution

1. Step 1: Understand duplicate handling

   The method compares current node value with max from right subtree, so duplicates do not affect max finding.

2. Step 2: Trace values

   Right subtree max is 15 (rightmost node). Root value 10 is less than 15, so max is 15.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Max value with duplicates = 15 [OK]

Hint: Compare node value with right subtree max for duplicates [OK]

Common Mistakes:

• Assuming duplicates cause errors
• Returning first max found without comparison
• Ignoring right subtree values