Difficulty : Medium Link: Day 12: May Leetcode Challenge

Problem Description Given the `root`

of a binary tree, return the level order traversal of its nodes’ values . (i.e., from left to right, level by level).

Examples Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Input: root = [1]
Output: [[1]]

Input: root = []
Output: []

Constraints The number of nodes in the tree is in the range `[0, 2000]`

. `-1000 <= Node.val <= 1000`

Solution Recursive The first approach could to start recursively since its intuitive. We can pass another parameter for level and further incrementing it by every call, thus marking the change of levels. This approach would of course we slow and for every new level we will have to iterate older levels every time.

Breadth-First Search A BFS approach involves the use of a data structure called Queue(q) so that we deal with the nodes of the tree in the proper order. The queue operates in a First In First Out (FIFO ) order, so insertions would be at the end and removing from the front. We can use that property and we can calculate the number of items to be processed in the next level by finding the count of elements in the queue after every iteration.

Swift class Solution { func levelOrder (_ root : TreeNode? ) -> [[Int ]] { guard let root = root else { return []} var queue = [TreeNode]() var output = [[Int ]]() queue.append (root) while queue.isEmpty == false { // start new level // number of elements in the current level var levelCount = queue.count var levelNodes = [Int ]() while levelCount > 0 { let node = queue.first ! queue.removeFirst () levelCount -= 1 levelNodes.append (node.val ) // Add Left child node if let left = node.left { queue.append (left) } // Add right child node if let right = node.right { queue.append (right) } } // Add nodes by level output.append (levelNodes) } return output } }

Python from collections import deque class Solution : def levelOrder (self , root ): """ :type root: TreeNode :rtype: List[List[int]] """ levels = [] if not root : return levels level = 0 queue = deque ([root ,]) while queue : # start the current level levels .append ([]) # number of elements in the current level level_length = len (queue ) for i in range (level_length ): node = queue .popleft () # fulfill the current level levels [level ].append (node .val ) # add child nodes of the current level # in the queue for the next level if node .left : queue .append (node .left ) if node .right : queue .append (node .right ) # go to next level level += 1 return levels

Java class Solution { public List< List< Integer >> levelOrder (TreeNode root) { List< List< Integer >> levels = new ArrayList< List< Integer >> (); if (root == null) return levels; Queue< TreeNode> queue = new LinkedList< TreeNode> (); queue.add (root); int level = 0 ; while ( ! queue.isEmpty () ) { // start the current level levels.add (new ArrayList< Integer > ()); // number of elements in the current level int level_length = queue.size (); for (int i = 0 ; i < level_length; ++ i) { TreeNode node = queue.remove (); // fulfill the current level levels.get (level).add (node.val ); // add child nodes of the current level // in the queue for the next level if (node.left != null) queue.add (node.left ); if (node.right != null) queue.add (node.right ); } // go to next level level++ ; } return levels; } }

Complexity Analysis Time complexity = O(N) since each node is processed exactly once.Space complexity = O(N) to keep the output structure which contains `N`

node values