BST Find Maximum Element in DSA Javascript

Mental Model

In a Binary Search Tree, the biggest number is always the rightmost node because bigger values go to the right.

Analogy: Imagine a line of people sorted by height, where the tallest person is always at the end of the line on the right side.

      10
     /  \
    5    15
          \
           20
            \
             25
             ↑ (start here)

Dry Run Walkthrough

Input: BST with nodes 10 -> 5, 15 -> 20 -> 25; find max element

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

Step 1: Start at root node 10

10 ↑ -> 5 -> 15 -> 20 -> 25 -> null

Why: We begin at the root to find the maximum

Step 2: Move right from 10 to 15

10 -> 5 -> 15 ↑ -> 20 -> 25 -> null

Why: Right child might have bigger value

Step 3: Move right from 15 to 20

10 -> 5 -> 15 -> 20 ↑ -> 25 -> null

Why: Keep moving right to find bigger values

Step 4: Move right from 20 to 25

10 -> 5 -> 15 -> 20 -> 25 ↑ -> null

Why: Continue moving right until no more right child

Step 5: No right child from 25, stop here

10 -> 5 -> 15 -> 20 -> 25 ↑ -> null

Why: Rightmost node is the maximum

Result:

10 -> 5 -> 15 -> 20 -> 25 ↑ -> null; Maximum element is 25

Annotated Code

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return;
        }
        current = current.right;
      }
    }
  }

  findMax() {
    if (!this.root) {
      return null;
    }
    let current = this.root;
    while (current.right) {
      current = current.right; // move right to find bigger value
    }
    return current.value; // rightmost node value is max
  }
}

// Driver code
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(20);
bst.insert(25);
console.log("Maximum element is", bst.findMax());

while (current.right) {

keep moving right to find the largest value

current = current.right; // move right to find bigger value

advance current pointer to right child

return current.value; // rightmost node value is max

return the value of the rightmost node

Output

Maximum element is 25

Complexity Analysis

Time: O(h) because we only move down the right children where h is tree height

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

vs Alternative: Compared to scanning all nodes O(n), this is faster since max is always rightmost

Edge Cases

Empty tree

Returns null because there is no maximum

DSA Javascript

if (!this.root) {
      return null;
    }

Tree with one node

Returns the single node's value as max

DSA Javascript

while (current.right) {
      current = current.right;
    }

When to Use This Pattern

When asked to find the maximum in a BST, look for the rightmost node because BSTs keep bigger values on the right.

Common Mistakes

Mistake: Trying to check left children or scanning entire tree for max
Fix: Only move right until no more right child to find max efficiently

Summary

Finds the largest value in a BST by moving right until no more right child.

Use when you need the maximum element quickly in a BST.

The maximum is always the rightmost node in a BST.