gistfile1.txt

Algorithm: Find the 2nd largest element in a binary search tree - 
based on the blog: 
https://www.interviewcake.com/question/python/second-largest-item-in-bst?utm_source=weekly_email&utm_source=drip&utm_campaign=weekly_email&utm_campaign=Interview%20Cake%20Weekly%20Problem%20%23183:%202nd%20Largest%20Item%20in%20a%20Binary%20Search%20Tree&utm_medium=email&utm_medium=email

What I like to do it to create a gist for the algorithm. 

We start with a function for getting the largest value. The largest value is simply the "rightmost" one, 
so we can get it in one walk down the tree by traversing rightward until we don't have a right child anymore:

  def find_largest(root_node):
    current = root_node
    while current:
        if not current.right:
            return current.value
        current = current.right

With this in mind, we can also find the second largest in one walk down the tree. At each step, 
we have a few cases:

If we have a left subtree but not a right subtree, then the current node is the largest overall 
(the "rightmost") node. The second largest element must be the largest element in the left subtree. 
We use our find_largest() function above to find the largest in that left subtree!
If we have a right child, but that right child node doesn't have any children, then the right child 
must be the largest element and our current node must be the second largest element!
Else, we have a right subtree with more than one element, so the largest and second largest are 
somewhere in that subtree. So we step right.

  def find_largest(root_node):
    current = root_node
    while current:
        if not current.right:
            return current.value
        current = current.right


def find_second_largest(root_node):
    if (root_node is None or
            (root_node.left is None and root_node.right is None)):
        raise ValueError('Tree must have at least 2 nodes')

    current = root_node
    while current:
        # Case: current is largest and has a left subtree
        # 2nd largest is the largest in that subtree
        if current.left and not current.right:
            return find_largest(current.left)

        # Case: current is parent of largest, and largest has no children,
        # so current is 2nd largest
        if (current.right and
                not current.right.left and
                not current.right.right):
            return current.value

        current = current.right

Complexity
We're doing one walk down our BST, which means O(h) time, where hh is the height of the tree 
(again, that's O(\lg{n}) if the tree is balanced, O(n) otherwise). O(1) space.

**What We Learned**
Here we used a "simplify, solve, and adapt" strategy.

The question asks for a function to find the second largest element in a BST, so we started off by 
simplifying the problem: we thought about how to find the first largest element.

Once we had a strategy for that, we adapted that strategy to work for finding the second largest element.

It may seem counter-intuitive to start off by solving the wrong question. But starting off with a simpler 
version of the problem is often much faster, because it's easier to wrap our heads around right away.

One more note about this one:

Breaking things down into cases is another strategy that really helped us here.

Notice how simple finding the second largest node got when we divided it into two cases:

The largest node has a left subtree.
The largest node does not have a left subtree.
Whenever a problem is starting to feel complicated, try breaking it down into cases.

It can be really helpful to actually draw out sample inputs for those cases. This'll keep your 
thinking organized and also help get your interviewer on the same page.

**What Julia likes to write down **
I like the presentation by interviewcake.com. My understanding is different. Try to define what subproblems
included in order to solve the problem. And also ask myself when the root node is the answer. Otherwise try
to think recursively.