BST Find Maximum Element in DSA Typescript

Mental Model

In a Binary Search Tree, the biggest number is always found by going as far right as possible.

Analogy: Imagine a family tree where older generations are on the left and younger generations on the right. The youngest person is the one farthest to the right.

      10
     /  \
    5    15
         /  \
        12   20
               
               ↑ (maximum)

Dry Run Walkthrough

Input: BST with nodes: 10 -> 5, 15 -> 12, 20; find maximum element

Goal: Find the largest value in the BST by moving right until no more right child exists

Step 1: Start at root node 10

10 -> 5 (left), 15 (right) ↑

Why: We begin at the root to find the maximum

Step 2: Move right from 10 to 15

15 -> 12 (left), 20 (right) ↑

Why: Maximum is always in the right subtree

Step 3: Move right from 15 to 20

20 ↑

Why: Keep moving right to find the largest value

Step 4: No right child of 20, stop here

20 ↑

Why: Reached the rightmost node, which is the maximum

Result:

20

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function findMax(root: TreeNode | null): number | null {
  if (root === null) return null; // empty tree
  let current = root;
  while (current.right !== null) {
    current = current.right; // move right to find max
  }
  return current.val; // rightmost node value
}

// Driver code
const root = new TreeNode(10,
  new TreeNode(5),
  new TreeNode(15, new TreeNode(12), new TreeNode(20))
);
const maxVal = findMax(root);
console.log(maxVal !== null ? maxVal.toString() : "Tree is empty");

if (root === null) return null; // empty tree

handle empty tree edge case

while (current.right !== null) {

keep moving right to find the maximum value

current = current.right; // move right to find max

advance current pointer to right child

return current.val; // rightmost node value

return the value of the rightmost node

Output

20

Complexity Analysis

Time: O(h) because we traverse down the height of the tree following right children only

Space: O(1) because we use only a few variables and no extra data structures

vs Alternative: Compared to searching all nodes (O(n)), this is faster since max is always rightmost, so we skip left subtrees

Edge Cases

Empty tree (root is null)

Returns null indicating no maximum value

DSA Typescript

if (root === null) return null; // empty tree

Tree with only one node

Returns the single node's value as maximum

DSA Typescript

while (current.right !== null) {

Tree where all nodes are left children (no right child)

Returns root value as maximum since no right child exists

DSA Typescript

while (current.right !== null) {

When to Use This Pattern

When you need the largest value in a BST, look for the rightmost node by following right children until none remain.

Common Mistakes

Mistake: Trying to check left children or searching entire tree for max
Fix: Only follow right children because BST property guarantees max is rightmost

Summary

Finds the maximum value in a BST by moving right until no right child exists.

Use when you want the largest element quickly in a BST.

The maximum is always the rightmost node in a BST.

Practice

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

easy

A. At the rightmost node

B. At the leftmost node

C. At the root node

D. At any leaf node

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes are smaller and right child nodes are larger than the parent node.

2. Step 2: Locate maximum element

   The maximum element is found by moving to the rightmost node because it has the largest value.

3. Final Answer:

   At the rightmost node -> Option A

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

easy

A. while(node.right !== null) { node = node.right; } return node.value;

B. return Math.max(node.value, findMax(node.left), findMax(node.right));

C. if(node.left === null) return node.value; else return findMax(node.left);

D. while(node.left !== null) { node = node.left; } return node.value;

Solution

1. Step 1: Identify correct traversal direction

   To find maximum in BST, traverse right child nodes until no more right child exists.

2. Step 2: Check code correctness

   while(node.right !== null) { node = node.right; } return node.value; uses a while loop to move right until right child is null, then returns node value.

3. Final Answer:

   while(node.right !== null) { node = node.right; } return node.value; -> Option A

4. Quick Check:

   Traverse right until null, then return value [OK]

Hint: Traverse right child nodes until none left [OK]

Common Mistakes:

• Traversing left instead of right
• Using recursion incorrectly
• Using Math.max on subtree values (not BST property)

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

class Node {
  constructor(public value: number, public left: Node | null = null, public right: Node | null = null) {}
}

function findMax(node: Node): number {
  while(node.right !== null) {
    node = node.right;
  }
  return node.value;
}

const root = new Node(10, new Node(5), new Node(15, null, new Node(20)));
console.log(findMax(root));

medium

A. 10

B. 5

C. 15

D. 20

Solution

1. Step 1: Understand tree structure

   Root is 10, left child 5, right child 15, and 15's right child is 20.

2. Step 2: Trace findMax function

   Function moves right from 10 to 15, then to 20, which has no right child, so returns 20.

3. Final Answer:

   20 -> Option D

4. Quick Check:

   Rightmost node value = 20 [OK]

Hint: Rightmost node value is maximum [OK]

Common Mistakes:

• Returning root value instead of rightmost
• Confusing left and right children
• Not following right child chain fully

4. The following TypeScript function is intended to find the maximum element in a BST. What is the error?

function findMax(node: Node): number {
  while(node.left !== null) {
    node = node.left;
  }
  return node.value;
}

medium

A. It returns undefined because node.value is missing

B. It causes infinite loop if node.left is null

C. It traverses left instead of right, so returns minimum instead of maximum

D. It throws error because Node type is incorrect

Solution

1. Step 1: Analyze traversal direction

   The function moves left child nodes, which leads to the minimum element in BST.

2. Step 2: Identify correct traversal for maximum

   Maximum element requires moving right child nodes, not left.

3. Final Answer:

   It traverses left instead of right, so returns minimum instead of maximum -> Option C

4. Quick Check:

   Left traversal = minimum, not maximum [OK]

Hint: Traverse right for max, left for min [OK]

Common Mistakes:

• Confusing left and right child traversal
• Assuming left traversal finds maximum
• Ignoring BST property of ordering

5. Given a BST where some nodes have only left children, how would you modify the findMax function to correctly find the maximum element even if the tree is skewed left?

hard

A. Return the root node's value directly since left skew means root is max

B. Traverse right child nodes until null; if none, return current node's value

C. Traverse left child nodes until null and return that value

D. Use recursion: return Math.max(node.value, findMax(node.left));

Solution

1. Step 1: Understand left skewed BST

   In a BST, values in left subtree < node <= values in right subtree. Even if some nodes have no right children, the maximum is found by traversing right until null.

2. Step 2: Modify findMax logic

   Traverse right child nodes until null; if no right child exists, current node is max.

3. Final Answer:

   Traverse right child nodes until null; if none, return current node's value -> Option B

4. Quick Check:

   Right traversal or current node if no right child [OK]

Hint: Check right child; if none, current node is max [OK]

Common Mistakes:

• Assuming root is always max in left skew
• Traversing left to find max
• Using recursion unnecessarily for simple right traversal