Balanced Binary 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 see if a binary tree ↴

A binary tree is a tree where every node has two or fewer children. The children are usually called left and right.

@interface ICKBinaryTreeNode : NSObject @property (nonatomic) NSInteger value; @property (nonatomic) ICKBinaryTreeNode *left; @property (nonatomic) ICKBinaryTreeNode *right; @end @implementation ICKBinaryTreeNode @end

This lets us build a structure like this:

That particular example is special because every level of the tree is completely full. There are no "gaps." We call this kind of tree "perfect."

Binary trees have a few interesting properties when they're perfect:

Property 1: the number of total nodes on each "level" doubles as we move down the tree.

Property 2: the number of nodes on the last level is equal to the sum of the number of nodes on all other levels (plus 1). In other words, about half of our nodes are on the last level.

Let's call the number of nodes $n$ , and the height of the tree $h$ . $h$ can also be thought of as the "number of levels."

If we had $h$ , how could we calculate $n$ ?

Let's just add up the number of nodes on each level! How many nodes are on each level?

If we zero-index the levels, the number of nodes on the $x$ th level is exactly $2^x$ .

Level $0$ : $2^0$ nodes,

Level $1$ : $2^1$ nodes,

Level $2$ : $2^2$ nodes,

Level $3$ : $2^3$ nodes,

etc

So our total number of nodes is:
$n = 2^0 + 2^1 + 2^2 + 2^3 + ... + 2^{h-1}$
Why only up to $2^{h-1}$ ? Notice that we started counting our levels at 0. So if we have $h$ levels in total, the last level is actually the " $h-1$ "-th level. That means the number of nodes on the last level is $2^{h-1}$ .

But we can simplify. Property 2 tells us that the number of nodes on the last level is (1 more than) half of the total number of nodes, so we can just take the number of nodes on the last level, multiply it by 2, and subtract 1 to get the number of nodes overall. We know the number of nodes on the last level is $2^{h-1}$ , So:
$n = 2^{h-1} * 2 - 1$ $n = 2^{h-1} * 2^1 - 1$ $n = 2^{h-1+1}- 1$ $n = 2^{h} - 1$
So that's how we can go from $h$ to $n$ . What about the other direction?

We need to bring the $h$ down from the exponent. That's what logs are for!

First, some quick review. $\log_{10} (100)$ simply means, "What power must you raise 10 to in order to get 100?". Which is 2, because $10^2 = 100$ .

We can use logs in algebra to bring variables down from exponents by exploiting the fact that we can simplify $\log_{10}(10^2)$ . What power must we raise $10$ to in order to get $10^2$ ? That's easy—it's $2$ .

So in this case we can take the $\log_{2}$ of both sides:
$n = 2^{h} - 1$ $n + 1 = 2^{h}$ $\log_{2}{((n+1))} = \log_{2}{(2^{h})}$ $\log_{2}{(n+1)} = h$
So that's the relationship between height and total nodes in a perfect binary tree.

is "superbalanced" (a new tree property we just made up).

A tree is "superbalanced" if the difference between the depths of any two leaf nodes ↴

A leaf node is a tree node with no children.

It's the "end" of a path to the bottom, from the root.

is no greater than one.

Here's a sample binary tree node class:

  @interface ICKBinaryTreeNode : NSObject
@property (nonatomic) NSInteger value;
@property (nonatomic) ICKBinaryTreeNode *left;
@property (nonatomic) ICKBinaryTreeNode *right;
- (instancetype)initWithValue:(NSInteger)value;
- (ICKBinaryTreeNode*)insertLeft:(NSInteger)leftValue;
- (ICKBinaryTreeNode*)insertRight:(NSInteger)rightValue;
@end

@implementation ICKBinaryTreeNode

- (instancetype)initWithValue:(NSInteger)value {
    if (self = [super init]) {
        self.value = value;
    }
    return self;
}

- (ICKBinaryTreeNode*)insertLeft:(NSInteger)leftValue {
    self.left = [[ICKBinaryTreeNode alloc] initWithValue:leftValue];
    return self.left;
}

- (ICKBinaryTreeNode*)insertRight:(NSInteger)rightValue {
    self.right = [[ICKBinaryTreeNode alloc] initWithValue:rightValue];
    return self.right;
}

@end

Gotchas

Your first thought might be to write a recursive function, thinking, "the tree is balanced if the left subtree is balanced and the right subtree is balanced." This kind of approach works well for some other tree problems.

But this isn't quite true. Counterexample: suppose that from the root of our tree:

The left subtree only has leaves at depths 10 and 11.
The right subtree only has leaves at depths 11 and 12.

Both subtrees are balanced, but from the root we will have leaves at 3 different depths.

We could instead have our recursive function get the array of distinct leaf depths for each subtree. That could work fine. But let's come up with an iterative solution instead. It's usually better to use an iterative solution instead of a recursive one because it avoids stack overflow. ↴

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 Objective-C. Here it is in Python 2.7:

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

ICKRollTwoAndSum()

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

ICKRollDie()

ICKRollTwoAndSum()

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

random.randint()

ICKRollDie()

ICKRollTwoAndSum()

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

ICKRollDie()

ICKRollTwoAndSum()

Same thing when ICKRollDie() returns:

ICKRollTwoAndSum()

We're not done yet! ICKRollTwoAndSum() calls ICKRollDie() again:

ICKRollDie()

ICKRollTwoAndSum()

Which calls random.randint() again:

random.randint()

ICKRollDie()

ICKRollTwoAndSum()

random.randint() returns, then ICKRollDie() returns, putting us back in ICKRollTwoAndSum():

ICKRollTwoAndSum()

Which calls print():

print()

ICKRollTwoAndSum()

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:

  NSUInteger ICKProduct1ToN(NSUInteger n) {
    return (n > 1) ? n * ICKProduct1ToN(n - 1) : 1;
}

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

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

    ICKProduct1ToN()    n = 10

This calls ICKProduct1ToN() with n = 9.

    ICKProduct1ToN()    n = 9

    ICKProduct1ToN()    n = 10

Which calls ICKProduct1ToN() with n = 8.

    ICKProduct1ToN()    n = 8

    ICKProduct1ToN()    n = 9

    ICKProduct1ToN()    n = 10

And so on until we get to n = 1.

    ICKProduct1ToN()    n = 1

    ICKProduct1ToN()    n = 2

    ICKProduct1ToN()    n = 3

    ICKProduct1ToN()    n = 4

    ICKProduct1ToN()    n = 5

    ICKProduct1ToN()    n = 6

    ICKProduct1ToN()    n = 7

    ICKProduct1ToN()    n = 8

    ICKProduct1ToN()    n = 9

    ICKProduct1ToN()    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?

  NSUInteger ICKProduct1ToN(NSUInteger n) {
    NSUInteger result = 1;

    for (NSUInteger 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:

    ICKProduct1ToN()    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.

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

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

    ICKProduct1ToN()    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.

We can do this in $O(n)$ time and $O(n)$ space.

What about a tree with only one leaf node? Does your function handle that case properly?

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

$O(n)$ time and $O(n)$ space.

For time, the worst case is the tree is balanced and we have to iterate over all $n$ nodes to make sure.

For the space cost, we have two data structures to watch: depths and nodes.

depths will never hold more than three elements, so we can write that off as $O(1)$ .

Because we’re doing a depth first search, nodes will hold at most $d$ nodes where $d$ is the depth of the tree (the number of levels in the tree from the root node down to the lowest node). So we could say our space cost is $O(d)$ .

But we can also relate $d$ to $n$ . In a balanced tree, $d$ is $O(\log_{2}(n))$ . And the more unbalanced the tree gets, the closer $d$ gets to $n$ .

In the worst case, the tree is a straight line of right children from the root where every node in that line also has a left child. The traversal will walk down the line of right children, adding a new left child to nodes at each step. When the traversal hits the rightmost node, nodes will hold half of the $n$ total nodes in the tree. Half $n$ is $O(n)$ , so our worst case space cost is $O(n)$ .

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).

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: