Problem 🤔

This is a warm up problem for binary search trees. Let’s write an algorithm to find the largest node in the tree! Finding the minimum is the exact same (just completely opposite lol) with a few tweaks ;)

Real World Applications 🌎

What’s the point of having a sorted data structure if we can’t get max? Okay, so this one is fairly straight forward, we want the maximum / min elements often.

Let’s remember, an inorder traversal will always yield all the elements of the tree in ascending order. Great! So essentially, we’re looking for the first and last element in the tree.

The Finer Details 🔎

The largest value in a binary search tree is always the right most one! Right?

Let’s build intuition for this statement and prove this statement by assuming that this isn’t true. Let’s assume for a moment that the largest node is:

1. An ancestor - If the largest is an ancestor of the rightest node that means that the rightest node is in the subtree of ancestor. But if ancestor >> rightest node that breaks the rules of a valid subtree! Therefore this can’t be.
2. Rightest node has a left sub tree - By the definition of left subtree all nodes are smaller or equal! So this would also break the defintion of a valid sub tree!
3. Rightest node has a right node - Well that doesn’t make sense does it? :)

Recursive Solution 💡

Complexity Analysis 🧮

Time complexity

O(n)

Worst case. Imagine a completely unbalanced BST where there are only right children! We’d need to traverse the whole tree.

Space complexity

O(n)

For a completely unbalanced tree, the stack size incurred for the recursion could be of length n.

Iterative Solution 💡

Complexity Analysis 🧮

Time complexity

O(n)

Worst case. Imagine a completely unbalanced BST where there are only right children!

Space complexity

O(1)

No extra space allocated.

Takeaways 🎉🥳

• The largest node in a binary search tree is always the right most node!