Find the maximum binary search tree node

You're working through a warm-up question at an IBM interview. The interviewer draws a tree on the whiteboard, labels the nodes with numbers that follow the left-smaller, right-larger pattern, and asks: "How would you find the largest value in this tree without checking every node?" This is a fundamental BST question that tests whether you understand the ordering property well enough to exploit it for better-than-linear performance. It is also known as "Find Maximum Value in BST" on other platforms.

TL;DR

In a binary search tree, the maximum value always lives at the rightmost node. Recursively follow root.right until you hit a node with no right child, then return that node's data. This runs in O(log n) time and O(log n) space for a balanced tree. The key insight is that the BST ordering property guarantees larger values are always to the right, so there is no need to visit any left subtrees.

Why This Problem Matters

Finding the maximum in a BST is one of the first problems that teaches you to leverage data structure properties for efficiency. A naive approach would scan every node in O(n) time, but the BST ordering rule lets us do much better. This same "follow the structure" thinking applies to BST deletion (where you need the in-order predecessor), range queries, and validation problems. The same pattern applies directly to BST deletion, range queries, and successor/predecessor lookups.

Binary Search Trees: The Ordering Property

Before solving this problem, let's make sure the BST property is clear. In a binary search tree, every node satisfies one rule: all values in the left subtree are smaller, and all values in the right subtree are larger.

Notice how the smallest value (4) sits at the far left and the largest value (16) sits at the far right. This is not a coincidence. The ordering property forces values to distribute this way. If you start at the root and always go right, you are always moving toward larger values. If you always go left, you move toward smaller values.

This property is what makes BSTs useful for search, insertion, and deletion in O(log n) time. And it is exactly what we will exploit to find the maximum without examining every node.

Understanding the Problem

Given: The root TreeNode of a binary search tree Task: Return the maximum data value in the tree Constraint: The tree has at least 1 node and at most 1000 nodes. Aim for better than linear time and space.

Here is the example from the problem:

The tree above has values 4, 5, 6, 10, 14, 15, and 16. The maximum is 16, which sits at the bottom-right. We want to find it without visiting the left subtrees at all.

Edge Cases to Consider

1. Single node: The root itself is the maximum
2. Right-skewed tree: Every node only has a right child, so we traverse every node
3. Left-skewed tree: The root has no right child, so the root is the maximum
4. Balanced tree: We only traverse O(log n) nodes down the right spine

Solution Approach

The strategy is straightforward once you internalize the BST property. Since larger values are always to the right, the maximum must be the rightmost node in the tree. There is no reason to look left at any point.

Building Intuition

Think of it like finding the last house on a one-way street that only turns right. You start at the beginning and keep turning right at every intersection. When there are no more right turns, you have arrived at the last house.

In BST terms:

1. If the current node has a right child, the maximum must be somewhere in the right subtree.
2. If the current node has no right child, this node holds the maximum.

That's the entire algorithm. Two cases, one recursive call.

Tracing the Path

Let's trace through the example BST to see the algorithm in action:

Starting at root (10), we check: does 10 have a right child? Yes, it is 15. Move right. Does 15 have a right child? Yes, it is 16. Move right. Does 16 have a right child? No. Return 16 as the maximum.

We visited exactly 3 nodes out of 7. For a balanced BST, this is typical: you only walk down the right spine, which has O(log n) nodes.

The Single-Node Case

When the tree has just one node, the base case handles it immediately:

The root has no right child, so we return its data right away. No recursion needed.

Implementation

Prefer a different language? Jump to solutions in other languages.

Here is the Java solution:

public class Solution {
  public int maxData(TreeNode root) {
    // Base case: no right child means this node holds the maximum
    if (root.right == null) {
      return root.data;
    }
    // Recursive case: the maximum is somewhere in the right subtree
    return maxData(root.right);
  }
}

Let's walk through this with the test case BST 4 2 8 # # 5 10:

Call 1: maxData(4) - root.right is 8, not null. Recurse on 8. Call 2: maxData(8) - root.right is 10, not null. Recurse on 10. Call 3: maxData(10) - root.right is null. Return 10.

The answer propagates back up the call stack: 10 is returned to call 2, then to call 1, then to the caller. Three calls, three nodes visited, O(log n) work.

The Iterative Alternative

You can also solve this with a simple loop, which avoids the recursive call stack:

public class Solution {
  public int maxData(TreeNode root) {
    while (root.right != null) {
      root = root.right;
    }
    return root.data;
  }
}

This is O(1) space instead of O(log n), since there is no recursion. Both approaches are valid in an interview. The recursive version is more elegant and maps directly to the problem structure. The iterative version is more space-efficient. Mentioning both shows solid engineering judgment.

Complexity Analysis

Time Complexity: O(log n)

For a balanced BST, the right spine has O(log n) nodes. We visit each of them exactly once, performing O(1) work per node (one comparison and one recursive call). So the total time is O(log n).

In the worst case, a right-skewed tree, every node lies on the right spine:

Here the tree degrades to a linked list, and we visit all n nodes, giving O(n) time. This worst case is important to mention in an interview, but for balanced BSTs (which are the common case with self-balancing trees like AVL or Red-Black trees), the O(log n) bound holds.

Space Complexity: O(log n)

The recursive approach uses stack frames proportional to the recursion depth, which equals the height of the tree. For a balanced BST, the height is O(log n). For a skewed tree, it is O(n).

The iterative approach uses O(1) space since it only needs a single pointer variable.

Common Pitfalls

1. Checking both subtrees: Some candidates visit both left and right children and compare. This works but wastes time. The BST property guarantees the max is always to the right. There is no need to look left.

2. Forgetting the base case: If you recurse without checking root.right == null, you will hit a NullPointerException when you try to access root.right.right on a leaf node.

3. Returning the node instead of the data: The problem asks for the maximum value (int), not the node itself. Make sure you return root.data, not root.

4. Assuming the root is the max: The root of a BST is the median-ish value, not the maximum. The max is always the rightmost node.

Interview Tips

When solving this problem in an interview:

1. State the BST property upfront: "In a BST, all values to the right are larger. So the maximum must be the rightmost node." This shows you understand the data structure.

2. Mention both approaches: Present the recursive solution, then mention the iterative alternative with its O(1) space advantage.

3. Discuss edge cases: Single node, skewed trees, and balanced trees. Show you think about degenerate inputs.

4. Connect to harder problems: "This same technique of following the BST structure is used in deletion, where I'd find the in-order predecessor by calling maxData on the left subtree."

5. If asked about the minimum: Explain it is the mirror operation, traversing left instead of right.

Key Takeaways

• The BST ordering property guarantees the maximum value is at the rightmost node. Exploiting this avoids scanning all n nodes.
• The recursive solution has two cases: base case (root.right == null, return root.data) and recursive case (recurse on root.right). Nothing else is needed.
• Time complexity is O(log n) for balanced trees, O(n) for skewed trees. Space follows the same pattern due to the call stack.
• The iterative version (while root.right != null, go right) achieves O(1) space and is worth mentioning in interviews.
• This "follow the structure" pattern is a building block for BST deletion, range queries, and validation.

Solutions in Other Languages

Python

class Solution:
    def max_data(self, root: TreeNode) -> int:
        if root.right is None:
            return root.data
        return self.max_data(root.right)

JavaScript

class Solution {
  maxData(root) {
    if (root.right === null) {
      return root.data;
    }
    return this.maxData(root.right);
  }
}

TypeScript

class Solution {
  maxData(root: TreeNode): number {
    if (root.right === null) {
      return root.data;
    }
    return this.maxData(root.right);
  }
}

C++

class Solution {
public:
  int maxData(TreeNode *root) {
    if (root->right == nullptr) {
      return root->data;
    }
    return maxData(root->right);
  }
};

Go

func (s *Solution) MaxData(root *TreeNode) int {
    if root.Right == nil {
        return root.Data
    }
    return s.MaxData(root.Right)
}

Scala

class Solution {
  def maxData(root: TreeNode): Int = {
    if (root.right == null) {
      root.data
    } else {
      maxData(root.right)
    }
  }
}

Kotlin

class Solution {
    fun maxData(root: TreeNode?): Int {
        if (root?.right == null) {
            return root!!.data
        }
        return maxData(root.right)
    }
}

Swift

class Solution {
    func maxData(_ root: TreeNode?) -> Int {
        if root!.right == nil {
            return root!.data
        }
        return maxData(root!.right)
    }
}

Rust

impl Solution {
    pub fn max_data(&self, root: Option<Box<TreeNode>>) -> i32 {
        let node = root.unwrap();
        if node.right.is_none() {
            return node.data;
        }
        self.max_data(node.right)
    }
}

Ruby

class Solution
  def max_data(root)
    return root.data if root.right.nil?
    max_data(root.right)
  end
end

PHP

class Solution {
    public function maxData(TreeNode $root): int {
        if ($root->right === null) {
            return $root->data;
        }
        return $this->maxData($root->right);
    }
}

Dart

class Solution {
  int maxData(TreeNode? root) {
    if (root?.right == null) {
      return root!.data;
    }
    return maxData(root!.right);
  }
}

C#

public class Solution {
    public int maxData(TreeNode? root) {
        if (root.right == null) {
            return root.data;
        }
        return maxData(root.right);
    }
}

Practice Makes Perfect

Once you are comfortable finding the maximum in a BST, try these related problems to solidify your understanding of BST properties:

• Find the minimum value in a BST (mirror this approach, go left)
• Validate whether a binary tree is a valid BST
• Find the in-order successor of a given node
• Delete a node from a BST (uses max/min finding as a subroutine)

This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are just starting your interview prep or sharpening your tree algorithm skills, consistent practice with problems like this will build the pattern recognition you need.