Computing once instead of at every node

The difference between an O(n squared) tree solution and an O(n) one is usually where the measuring happens.

The natural but wasteful shape

Suppose every node must be checked against a property that depends on the height of its subtrees. The obvious code walks every node and, at each one, computes the heights from scratch.

That is the nested recursion from the last lesson, and here it is avoidable. Heights of a node's children are already computed while computing the height of the node itself, so recomputing them is pure waste.

Why it works

Return the measurement and the verdict together

Compute the height bottom-up in a single walk, and use an impossible height value to mean the property has already failed somewhere below.

Since a real height is never negative, -1 can carry that message. As soon as a subtree reports -1, every ancestor immediately reports -1 too, and the failure propagates to the top without any extra traversal.

1class T:2    def __init__(self, val, left=None, right=None):3        self.val, self.left, self.right = val, left, right4 5def uniform_leaf_depth(node):6    """Height if every leaf sits at the same depth, else -1."""7    if node is None:8        return 09    left = uniform_leaf_depth(node.left)10    if left == -1:11        return -1                       # already failed below12    right = uniform_leaf_depth(node.right)13    if right == -1:14        return -115    if left != right:16        return -1                       # fails right here17    return left + 118 19print(uniform_leaf_depth(T(1, T(2), T(3))))20print(uniform_leaf_depth(T(1, T(2, T(4)), T(3))))

Find the bug· 5 min

Find the wasted work

This checks whether every node's two subtrees hold the same number of nodes. It is O(n squared). Click the line that causes the extra factor.

Click the line you think is wrong

Problem· 22 min

Balanced Binary Tree

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

The natural but wasteful shape

Suppose every node must be checked against a property that depends on the height of its subtrees. The obvious code walks every node and, at each one, computes the heights from scratch.

1class T:2 def __init__(self, val, left=None, right=None):3 self.val, self.left, self.right = val, left, right4 5def uniform_leaf_depth(node):6 """Height if every leaf sits at the same depth, else -1."""7 if node is None:8 return 09 left = uniform_leaf_depth(node.left)10 if left == -1:11 return -1 # already failed below12 right = uniform_leaf_depth(node.right)13 if right == -1:14 return -115 if left != right:16 return -1 # fails right here17 return left + 118 19print(uniform_leaf_depth(T(1, T(2), T(3))))20print(uniform_leaf_depth(T(1, T(2, T(4)), T(3))))