Recursion and Trees
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.
Key idea
One return value doing two jobs
The returned number means two different things depending on its value: a real height, or a flag saying the answer is already known to be no.
That is a slightly uncomfortable design and it is standard, because it keeps the walk to a single pass. The alternative is returning a pair of a boolean and a height, which is clearer and marginally slower, and is perfectly acceptable if you prefer it.
Say which you are doing. An interviewer who sees -1 returned from a height function will want to know you chose it rather than copied it.
Cost
Why this is linear
Each node is visited exactly once and does constant work, so O(n) time. Space is the recursion depth, O(h) for height h.
Compare with the naive version: outer walk over n nodes, each computing heights over its whole subtree, which is O(n squared) on a degenerate tree. The entire saving comes from noticing that the recursive call already produces what the check needs.
Tip
The general lesson
Whenever a tree solution walks the tree to check a property that itself requires walking the tree, ask whether the inner measurement is already available from the outer recursion.
It usually is, because a postorder recursion has both children's answers in hand at the moment it needs to decide anything about the current node. That observation is also what the next lesson is built on.
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.
This activity type is not wired up yet.
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.