2nd Largest Item in a Binary Search Tree (Practice Interview Question)

You only have 3 free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

You're in!

Write a function to find the 2nd largest element in a binary search tree. ↴

Costs

Balanced Unbalanced (Worst Case)

space $O(n)$ $O(n)$

insert $O(lg(n))$ $O(n)$

lookup $O(lg(n))$ $O(n)$

delete $O(lg(n))$ $O(n)$

Quick reference

A binary search tree is a binary tree where the nodes are ordered in a specific way. For every node:

The nodes to the left are smaller than the current node.

The nodes to the right are larger than the current node.

Checking if a binary tree is a binary search tree is a favorite question from interviews.

Strengths:

Good performance across the board. Assuming they're balanced, binary search trees are good at lots of operations, even if they're not constant time for anything.

Compared to a sorted array, lookups take the same amount of time ( $O(lg(n))$ ), but inserts and deletes are faster ( $O(lg(n))$ for BSTs, $O(n)$ for arrays).

Compared to hash tables, BSTs have better worst case performance— $O(lg(n))$ instead of $O(n)$ . But, on average hash tables perform better than BSTs (meaning $O(1)$ time complexity).

BSTs are sorted. Taking a binary search tree and pulling out all of the elements in sorted order can be done in $O(n)$ using an in-order traversal. Finding the element closest to a value can be done in $O(lg(n))$ (again, if the BST is balanced!).

Weaknesses:

Poor performance if unbalanced. Some types of binary search trees balance automatically, but not all. If a BST is not balanced, then operations become $O(n)$ .

No $O(1)$ operations. BSTs aren't the fastest for anything. On average, an array or a hash table will be faster.

Balanced Binary Search Trees

Two binary search trees can store the same values in different ways:

Some trees (like AVL trees or Red-Black trees) rearrange nodes as they're inserted to ensure the tree is always balanced. With these, the worst case complexity for searching, inserting, or deleting is always $O(lg(n))$ , not $O(n)$ .

	Balanced	Unbalanced (Worst Case)
space	$O(n)$	$O(n)$
insert	$O(lg(n))$	$O(n)$
lookup	$O(lg(n))$	$O(n)$
delete	$O(lg(n))$	$O(n)$

Here's a sample binary tree implementation:

  typedef struct BinaryTreeNode {
    void *value;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
} BinaryTreeNode;

BinaryTreeNode * binaryTreeNodeNew(const void *value, size_t valueSize)
{
    BinaryTreeNode *node;

    node = malloc(sizeof(BinaryTreeNode));
    assert(node != NULL);

    node->value = malloc(valueSize);
    assert(node->value != NULL);
    memcpy(node->value, value, valueSize);

    node->left = NULL;
    node->right = NULL;

    return node;
}

BinaryTreeNode * binaryTreeNodeInsertLeft(BinaryTreeNode *treeRoot, const void *value, size_t valueSize)
{
    treeRoot->left = binaryTreeNodeNew(value, valueSize);
    return treeRoot->left;
}

BinaryTreeNode * binaryTreeNodeInsertRight(BinaryTreeNode *treeRoot, const void *value, size_t valueSize)
{
    treeRoot->right = binaryTreeNodeNew(value, valueSize);
    return treeRoot->right;
}

void binaryTreeNodeFree(BinaryTreeNode *treeRoot)
{
    if (treeRoot != NULL) {
        binaryTreeNodeFree(treeRoot->left);
        binaryTreeNodeFree(treeRoot->right);
        free(treeRoot->value);
        free(treeRoot);
    }
}

Gotchas

Our first thought might be to do an in-order traversal of the BST ↴

Sometimes we have a BST and we want to go through the items in order from smallest to largest. This is called an "in-order traversal."

We can write a recursive algorithm for this:

Everything in the left subtree is smaller, so print that first, then,
print the current node, then
print the right subtree.

  void inorderPrint(BinaryTreeNode* node)
{
    if (node != NULL) {
        inorderPrint(node->left);
        printf("%d\n", *(int *)node->value);
        inorderPrint(node->right);
    }
}

This takes $O(n)$ time (we're traversing the whole tree, so we're looking at all $n$ items) and $O(h)$ space, where $h$ is the height of the tree (this is the max depth of the call stack during our recursion).

If the tree is balanced its height is $lg(n)$ , so we have $O(lg(n))$ space. If we can't make any assumptions about the "shape" of the tree, in the worst case it's just one continuous line, giving us a height of $n$ , and a space complexity of $O(n)$ for our recursive in-order traversal.

and return the second-to-last item. This means looking at every node in the BST. That would take

O(n)

time and

O(h)

space, where

h

is the max height of the tree (which is

lg(n)

if the tree is balanced, ↴

Formally, a tree is said to be balanced if the difference between the depths of any node's left tree and right tree is no greater than 1.

Thus a 'balanced' tree 'looks full', without any apparent chunks missing or any branches that end much earlier than other branches.

but could be as much as

n

if not).

We can do better than $O(n)$ time and $O(h)$ space.

We can do this in one walk from top to bottom of our BST. This means $O(h)$ time (again, that's $O(\lg{n})$ if the tree is balanced, $O(n)$ otherwise).

A clean recursive implementation will take $O(h)$ space in the call stack, ↴

Overview

The call stack is what a program uses to keep track of function calls. The call stack is made up of stack frames—one for each function call.

For instance, say we called a function that rolled two dice and printed the sum.

  def roll_die():
    return random.randint(1, 6)

def roll_two_and_sum():
    total = 0
    total += roll_die()
    total += roll_die()
    print total

roll_two_and_sum()

We're still translating this code to C. Here it is in Python 2.7:

First, our program calls rollTwoAndSum(). It goes on the call stack:

rollTwoAndSum()

That function calls rollDie(), which gets pushed on to the top of the call stack:

rollDie()

rollTwoAndSum()

Inside of rollDie(), we call random.randint(). Here's what our call stack looks like then:

random.randint()

rollDie()

rollTwoAndSum()

When random.randint() finishes, we return back to rollDie() by removing ("popping") random.randint()'s stack frame.

rollDie()

rollTwoAndSum()

Same thing when rollDie() returns:

rollTwoAndSum()

We're not done yet! rollTwoAndSum() calls rollDie() again:

rollDie()

rollTwoAndSum()

Which calls random.randint() again:

random.randint()

rollDie()

rollTwoAndSum()

random.randint() returns, then rollDie() returns, putting us back in rollTwoAndSum():

rollTwoAndSum()

Which calls print():

print()

rollTwoAndSum()

What's stored in a stack frame?

What actually goes in a function's stack frame?

A stack frame usually stores:

Local variables
Arguments passed into the function
Information about the caller's stack frame
The return address—what the program should do after the function returns (i.e.: where it should "return to"). This is usually somewhere in the middle of the caller's code.

Some of the specifics vary between processor architectures. For instance, AMD64 (64-bit x86) processors pass some arguments in registers and some on the call stack. And, ARM processors (common in phones) store the return address in a special register instead of putting it on the call stack.

The Space Cost of Stack Frames

Each function call creates its own stack frame, taking up space on the call stack. That's important because it can impact the space complexity of an algorithm. Especially when we use recursion.

For example, if we wanted to multiply all the numbers between $1$ and $n$ , we could use this recursive approach:

  int product1ToN(int n)
{
    // we assume n >= 1
    return (n > 1) ? (n * product1ToN(n - 1)) : 1;
}

What would the call stack look like when n = 10?

First, product1ToN() gets called with n = 10:

    product1ToN()    n = 10

This calls product1ToN() with n = 9.

    product1ToN()    n = 9

    product1ToN()    n = 10

Which calls product1ToN() with n = 8.

    product1ToN()    n = 8

    product1ToN()    n = 9

    product1ToN()    n = 10

And so on until we get to n = 1.

    product1ToN()    n = 1

    product1ToN()    n = 2

    product1ToN()    n = 3

    product1ToN()    n = 4

    product1ToN()    n = 5

    product1ToN()    n = 6

    product1ToN()    n = 7

    product1ToN()    n = 8

    product1ToN()    n = 9

    product1ToN()    n = 10

Look at the size of all those stack frames! The entire call stack takes up $O(n)$ space. That's right—we have an $O(n)$ space cost even though our function itself doesn't create any data structures!

What if we'd used an iterative approach instead of a recursive one?

  int product1ToN(int n)
{
    // we assume n >= 1
    int num;
    int result = 1;

    for (num = 1; num <= n; num++) {
        result *= num;
    }

    return result;
}

This version takes a constant amount of space. At the beginning of the loop, the call stack looks like this:

    product1ToN()    n = 10, result = 1, num = 1

As we iterate through the loop, the local variables change, but we stay in the same stack frame because we don't call any other functions.

    product1ToN()    n = 10, result = 2, num = 2

    product1ToN()    n = 10, result = 6, num = 3

    product1ToN()    n = 10, result = 24, num = 4

In general, even though the compiler or interpreter will take care of managing the call stack for you, it's important to consider the depth of the call stack when analyzing the space complexity of an algorithm.

Be especially careful with recursive functions! They can end up building huge call stacks.

What happens if we run out of space? It's a stack overflow! In C, the program will just crash with a segfault.

If the very last thing a function does is call another function, then its stack frame might not be needed any more. The function could free up its stack frame before doing its final call, saving space.

This is called tail call optimization (TCO). If a recursive function is optimized with TCO, then it may not end up with a big call stack.

In general, most languages don't provide TCO. Scheme is one of the few languages that guarantee tail call optimization. Some Ruby, C, and Javascript implementations may do it. Python and Java decidedly don't.

but we can bring our algorithm down to

O(1)

space overall.

Breakdown

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Solution

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Complexity

We're doing one walk down our BST, which means $O(h)$ time, where $h$ 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

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Do you have an answer?

Show answer

I have an answer Tell me more

Ready for more?

Check out our full course

You only have 3 free questions left (including this one).

Costs

Quick reference

Strengths:

Weaknesses:

Balanced Binary Search Trees

Gotchas

Overview

What's stored in a stack frame?

The Space Cost of Stack Frames

Breakdown

Start your free trial!

Solution

Start your free trial!

Complexity

What We Learned

Start your free trial!

Ready for more?

Programming interview questions by company:

Programming interview questions by topic: