Problem 🤔

This is a warm up problem for binary search trees. Let’s write an algorithm to find the largest node in the tree! Then we can use this as a utility to find the second largest.

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.

The Finer Details 🔎

We’re going to use a really common strategy for solving recurisve problems. It’s especially common with binary tree type questions. We’re going to write a helper function. Once we have a few basic building blocks this will be much easier. So what would be a useful helper function? Having a util method for finding the largest node in the tree seems like it would be a good start!

For an in depth explanation on that, check out the Find Max and Min in BST post.

So, with a Find Largest Node in Tree helper handy what’s the strategy?

So there are 2 approaches here:

Naive Solution 💡

Traverse everything inorder, return the second to last node. This will definitley work but is O(n) runtime (we’re visiting all nodes!). Since the tree is sorted we can do better!

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. Tracking all n seen nodes is also a list of length n.

Solution 💡 - Recursion

Let’s try to understand what the second to largest node really looks like?

If the largest node is a leaf, the second largest node is its parents node. Now, what if the largest node has a left sub tree? Well, we can just use our utility function findLargest and call it a day!

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. Tracking all n seen nodes is also a list of length n. With a balanced tree though our recursive stack length will be O(log(n)), therefore this solution is more performant on average on the what we proposed above.

Takeaways 🎉🥳

Break the problem into smaller bits! Write util functions to lessen the cognitive load, this is a pattern in recursive / tree functions.