Just No more free questions left!

Upgrade Now
**
Write a function to see if a 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 is no greater than one.

Here's a sample binary tree node class:

class BinaryTreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert_left(self, value):
self.left = BinaryTreeNode(value)
return self.left
def insert_right(self, value):
self.right = BinaryTreeNode(value)
return self.right

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

We can do this in time and space.

We'll never post on your wall or message your friends.

Once you're logged in, you'll get free full access to this and 4 other questions.

We'll never post on your wall or message your friends.

Once you're logged in, you'll get free full access to this and 4 other questions.

time and 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 .

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 .

But we can also relate d to n. In a balanced tree, d is . 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 , so our worst case space cost is .

We'll never post on your wall or message your friends.

Once you're logged in, you'll get free full access to this and 4 other questions.

Powered by qualified.io

{"id":7165693,"username":"2018-01-17_10:39:56_6t1i08","email":null,"date_joined":"2018-01-17T10:39:56.218135+00:00","first_name":"","last_name":"","full_name":"","short_name":"friend","is_anonymous":true,"is_on_last_question":false,"percent_done":0,"num_questions_done":0,"num_questions_remaining":46,"recruiting_is_interested_in_intros":null,"is_full_access":false,"first_payment_date":null,"last_payment_date":null,"num_free_questions_left":3,"terms_has_agreed_to_latest":false,"preferred_content_language":"","preferred_editor_language":"","is_staff":false,"auth_providers_human_readable_list":"","num_auth_providers":0,"auth_email":"","profile_public_id":null}

. . .