Binary Tree BFS

Reader guide and study workflow · Complete course map

Begin with a question about the whole depth

A root has children A and B. A has children C and D; B has child E. We want one group per distance from the root. A direct recursive solution can carry depth and append to groups[depth]; that already solves the task. Why consider a queue? It can finish each group before starting the next, which lets us compute an average or successor links without first collecting every group.

Start a round with queue [A,B]. Remove A and append C,D: the queue becomes [B,C,D]. Its contents now mix two depths. If the loop keeps following the changing queue length, it has forgotten which nodes belonged to the original question. Saving size=2 records that boundary. Exactly two removals produce [A,B] and leave [C,D,E] for the next round.

The invariant belongs at a precise moment: at the start of an outer round, the queue contains exactly one depth in left-to-right order. During the round, processed nodes disappear and next-depth nodes accumulate. This is why a proof saying “the queue always contains one level” is false even when the program is correct.

Decide whether a variation changes discovery or the answer

For zigzag output, reverse [C,D,E] into [E,D,C]. There is no need to change which nodes are discovered next: write each dequeued value into index size-1-i for a reversed output level. Separating traversal order from placement avoids accidentally reversing both and canceling the intended effect. Repeatedly inserting at the front of a Go slice would also turn a wide level into quadratic copying.

The right-side view takes one value per depth, not one chain of Right pointers. Delete E from the drawing: D is now the deepest visible node even though it belongs to the root's left subtree. Averages need a fresh sum and the frozen count; successor links need every final Next explicitly set to nil, because output fields may already contain stale links.

Compare the memory promises

A depth-carrying DFS retains O(h) call frames; a queue retains a width-sized frontier (with backing-array details depending on queue implementation). Neither is uniformly smaller: compare a chain with a nearly complete tree. Next-link construction can use an already-correct current-level chain instead of a queue, but it must first establish and terminate that chain before trusting it. The ordinary child-pointer traversal requires no trust in incoming Next fields.

Prerequisites and readiness

Know FIFO queues, tree depth, and the difference between traversal order and output order. Be able to explain why a frozen frontier size defines one level.

Reasoning workshop: freeze the frontier

One queue invariant supports several outputs

At a level boundary, the queue contains exactly the next depth's nodes in left-to-right order. Save its size before adding children. Remove exactly that many nodes, appending each left child before its right child. Newly appended children belong to the next level and must not affect the current loop bound or average divisor.

Take root 1, children 2 and 3, with node 2 having right child 5 and node 3 having no children. The levels are [1], [2,3], [5]. The right-side view is [1,3,5], demonstrating that a deeper visible node can come from the root's left subtree. Following only Right links would miss node 5.

Change placement without changing discovery

Zigzag output does not require a complicated alternating traversal. Preserve ordinary left-to-right BFS discovery, then place the ith value at i on forward levels or size-1-i on reversed levels. For a discovered level [4,5,6,7], reverse placement yields [7,6,5,4]. Reversing both discovery and placement without a proof can cancel the intended reversal.

Averages use the same frontier, but require resetting the sum each depth and dividing in floating point. Values 2 and 3 average to 2.5; converting an already-truncated integer quotient is too late. The stated 32-bit values and at most 100000 nodes keep a level sum below 2^53 in magnitude, so the reference's int64 accumulation is safe and its conversion to float64 represents the integer sum exactly before division. Numerical tolerance still belongs in output tests.

Output pointers need full assignment

Connect writes a successor relation within each level. Link the previous node to the current one and explicitly terminate the last node with nil. The queue reference discovers children through Left and Right, not through initial Next links. That makes it robust to stale Next pointers, including self-links and links into the wrong depth. A second call must produce the same correct chains, not preserve stale terminal fields.

An O(1)-auxiliary next-level construction is possible by using established Next chains as traversal structure, but that is a different implementation and must carefully initialize and terminate those chains. The supplied queue implementation should not be documented as though it already uses the constant-space alternative.

Queue memory and complexity

Every node is enqueued and removed once, so traversal is O(n). The frontier can be wide; O(n) auxiliary memory is a safe worst-case bound for these queue references. Result storage is additional: LevelOrder and Zigzag return every value, while RightSideView and AverageOfLevels return one value per depth. A head-index queue avoids front deletion, but retained backing storage should still be included when discussing practical memory use.

For independent tests, traverse by depth using a recursive depth-indexed collector, then derive level order, reversed placement, rightmost values, and means from that collector. For Connect, compare exact pointer successors against each expected level and verify all child edges remain unchanged.

Reconstruction lab and answer key

Binary Tree Level Order Traversal

A level starts with queue [A,B]. A is a leaf; B has children C,D. The code runs for i=0; i<len(queue); i++ while removing the front. Which current-level node is skipped, and what invariant repairs the loop?

Model answer

After removing A, queue=[B] and i becomes 1. The condition 1<len(queue)=1 fails, so B is wrongly left for a later level. Capture size=2 before either removal and process exactly two nodes. The saved size refers to the original frontier, independent of whether processing nodes shrinks or grows the queue.

Binary Tree Zigzag Level Order Traversal

A reversed level is discovered as [10,20,30]. List the destination indices in dequeue order. If those nodes have children, in what order should their children be enqueued for this implementation?

Model answer

The destinations are 2,1,0, yielding [30,20,10]. Visit parent nodes in ordinary queue order and append each left child before its right child. Output reversal alone supplies zigzag; reversing child discovery too changes the invariant and would require a different proof.

Binary Tree Right Side View

Root 8 has left child 4 and right child 12. Node 4 has right child 6, and 6 has left child 5; node 12 is a leaf. Give the visible sequence and explain why following Right pointers fails.

Model answer

The view is [8,12,6,5]. Visibility chooses the rightmost existing node independently at each depth. At depths 2 and 3 there are no nodes from the root’s right subtree, so nodes 6 and 5 are visible. A root-to-rightmost-leaf chain contains only [8,12].

Average of Levels in Binary Tree

A level contains [−3,2,2]. What sum, divisor, and result should be used? Would float64(sum/count) and float64(sum)/float64(count) agree?

Model answer

The sum is 1, count is 3, and the mean is 1/3 within floating-point tolerance. Integer sum/count truncates to 0 before conversion, so the first expression is wrong. Convert before division. Reset the sum for the next level and use the saved level size, not a queue length that includes children.

Populating Next Right Pointers in Each Node II

Root R has children A,B; A has only right child C and B has only left child D. Incoming Next fields include B.Next=B and D.Next=A. What exact successor chains must remain, and which edges may be used to discover nodes safely?

Model answer

The chains are R→nil, A→B→nil, and C→D→nil. A child-pointer BFS discovers nodes through Left/Right, so it never trusts the stale Next self-cycle or cross-level link. It must write the nil at every level’s end and preserve all Left/Right edges. An O(1)-space variant must first establish a correct chain before traversing it.

Problems in this module

• Binary Tree Level Order Traversal
• Binary Tree Zigzag Level Order Traversal
• Binary Tree Right Side View
• Average of Levels in Binary Tree
• Populating Next Right Pointers in Each Node II

Interactive checkpoint

Open the Binary Tree BFS quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable