Binary Trees Breadth first: level by level
367. Binary Tree Level Order Traversal
You are given root, the root node of a binary tree. Return the values of its nodes level by level: a list
with one list for each level, from the top level down. Each level's list holds the values of that level's
nodes from left to right.
The root is the only node on the first level. Its children make up the second level, their children the
third, and so on. Nodes on the same level can have different parents. An empty tree has no levels, so the
answer is [].
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out.
Example 1
Input: root = [2, 8, -4, 6, null, 0, 3, null, null, null, null, 5]
[[2],[8,-4],[6,0,3],[5]]Explanation: 2 is alone at the top, and its children 8 and −4 make the second level. The third level is 6, 0 and 3. 6 is a child of 8, while 0 and 3 are children of −4. The last level is 5 alone.
Example 2
Input: root = []
[]Explanation: The tree has no nodes, so it has no levels.
Example 3
Input: root = [1000000000, -1000000000, null, 0]
[[1000000000],[-1000000000],[0]]Explanation: Each node has one child, so every level holds exactly one node.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
Clarifying questions
What you would ask an interviewer before writing any code.