TRT
Sign in

Core · Module 10 · Lesson 5 of 5

Level-order traversal

Visiting a tree level by level needs a queue instead of a stack. Taking a snapshot of the queue's size separates one level from the next, which solves a family of problems about depth, width and views.

Pro — members onlyAbout 12 minutes

By the end you can

  • Traverse a tree level by level with a queue, in O(n) time
  • Process exactly one level at a time by snapshotting the queue's length
  • Choose between breadth-first and depth-first traversal by result order and memory

Builds on Tree recursion patterns, Queues and ring buffers.

01 · A question first

To find the shallowest leaf in a tree of a million nodes, a depth-first search may wander down a branch thousands of levels deep before it finds anything. A level-by-level search stops at the first leaf it reaches. What makes it visit nodes in order of depth?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Breadth before depth
  • Why a queue gives level order
  • Processing one level at a time
  • Tracking depth without the snapshot
  • Levels as a tool
  • Memory: wide versus deep
  • Serializing trees
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeBinary tree level order traversalReturn a tree's values level by level, using a queue and the length of the queue at the start of each level.Practice · medium · LeetCodeBinary tree right side viewReturn the values visible from the right side of a tree: the last node of each level.Practice · easy · LeetCodeMinimum depth of binary treeFind the depth of the shallowest leaf, stopping a level-order traversal at the first leaf it meets.

Asked in interviews

Something wrong with this lesson? Report a problem