Recursion and Trees
Going across instead of down
A queue instead of the call stack, and the one line that turns a flat walk into levels.
Key idea
When depth-first is the wrong tool
Recursion naturally goes deep before it goes wide. Some questions are about the tree level by level: what is on each row, what is the leftmost node of each row, how far down is the nearest leaf.
Those want breadth-first traversal, which visits everything at one depth before moving to the next. It uses an explicit queue rather than the call stack.
Tip
That output is flat, and usually you want levels
The walk visits in the right order and throws away the level boundaries. 2 and 3 are the second row and 4 and 5 are the third, and nothing in that flat list says where one row ends.
Recovering the boundaries takes one extra line, and it is the thing worth remembering from this lesson.
Why it works
Snapshot the queue length
At the top of each round, the queue holds exactly the nodes of the current level and nothing else. So record its length before processing, then process exactly that many nodes.
Everything added during those steps belongs to the next level, and it lands behind the ones you are still processing. The invariant is: at the start of each round, the queue is precisely one level.
Here is the same flat walk as before, except that the snapshot makes it possible to say which level each value came from.
Gotcha
Read the length before the loop, not inside it
Writing for _ in range(len(queue)) evaluates the length once at the start, which is correct. Writing while len(queue) > 0 inside the level loop is not: the queue grows as children are added and the level never ends.
The bug produces one enormous level containing the whole tree. If a level-order solution returns a single row, this is why.
Key idea
What each variant reads off a level
Once you have levels, most of the family is a one-line change to what you record. The whole row gives level order. The last element of each row gives the view from the right; the first gives the view from the left. The row's length, maximum, or average each answer a different question.
Both problems below are this loop with a different line in the middle, which is why they sit together.
Cost
Cost
Every node enters and leaves the queue once, so O(n) time. The queue holds at most one level at a time, and the widest level of a balanced tree is about half the nodes, so the space is O(n) in the worst case.
That is worth contrasting with depth-first, whose space is the height rather than the width. Neither is universally cheaper; wide shallow trees favor recursion and deep narrow ones favor a queue.
Level drills
Three readings of the same loop. level_sums returns the sum of each level. widest_level returns the number of nodes on the widest level. leftmost_per_level returns the first value on each level.
Tests
tree = T(1, T(2, T(4), T(5)), T(3)) print(level_sums(tree), level_sums(None)) print(widest_level(tree), widest_level(None), widest_level(T(9))) print(leftmost_per_level(tree), leftmost_per_level(None))
Output
Run the tests when you are ready.
Binary Tree Level Order Traversal
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.
Binary Tree Right Side View
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.