trees · Problem 2 of 3

Binary Tree Level Order Traversal

medium
Amazon logoAmazon
Meta logoMeta
Microsoft logoMicrosoft
Bloomberg logoBloomberg

A binary tree node is represented as { value, left, right }, with null for a missing child.

Return the level order traversal of its nodes values (i.e., from left to right, level by level).

levelOrder({
  value: 3,
  left: { value: 9, left: null, right: null },
  right: {
    value: 20,
    left: { value: 15, left: null, right: null },
    right: { value: 7, left: null, right: null }
  }
})  ->  [[3], [9, 20], [15, 7]]

Your solution

Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.

Running is free — Submit is what records it. Or press ⌘↩

Tests

4 cases, 1 hidden
calltypeexpectedresult
levelOrder(null)empty[]—
levelOrder({"value":1,"left":null,"right":null})single node[[1]]—
levelOrder({"value":3,"left":{"value":9,"left":null,"right":null},"right":{"value":20,"left":{"value":15,"left":null,"right":null},"right":{"value":7,"left":null,"right":null}}})three levels[[3],[9,20],[15,7]]—
withheldhiddenwithheld—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Complexity

target time
O(n)
target space
O(n)

Each node is enqueued and dequeued once. In the worst case (full binary tree), the queue holds up to n/2 nodes at the leaf level.

Hints

Stuck? Hints open one at a time, each giving a little more away.

3 hints left