Solution by sneha29shukla


  • 0
    S

    Approach #1 Recursive Solution (BFS) [Accepted]

    Intuition

    The intuition is simple BFS. We first find the height of the tree, and then for each level in the tree, keep adding the nodes to a list, which is added to a final list of lists, as required by the signature of the solution.

    Java

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
    
            if(root == null) {
                return result;
            }
    
            Integer height = findHeight(root);
    
            for(int i = 1; i <= height; i++) {
                result.add(getNodesAtLevel(root, i, new ArrayList<Integer>()));
            }
    
            return result;
        }
    
        private static Integer findHeight(TreeNode root) {
            if(root == null) {
                return 0;
            }
    
            Integer lHeight = findHeight(root.left);
            Integer rHeight = findHeight(root.right);
    
            if(lHeight > rHeight)
                return lHeight + 1;
            else
                return rHeight + 1;
        }
    
        private static List<Integer> getNodesAtLevel(TreeNode root, Integer level, ArrayList<Integer> result) {
            if(root == null) {
                return result;
            }
    
            if(level == 1) {
                result.add(root.val);
            }
    
            getNodesAtLevel(root.left, level - 1, result);
            getNodesAtLevel(root.right, level - 1, result);
    
            return result;
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n^2).

    The time complexity can be O(n^2) in the worst case. That is because, the getNodesAtLevel function has a complexity of O(n) for a skewed tree of n nodes. In the worst case it would be O(n) + O(n - 1).... and hence, O(n^2).

    • Space complexity : The extra space for this solution comes only from the stack maintained by recursion.

    Approach #2 Using a Queue [Accepted]

    Algorithm

    • Create an empty queue and add root to it
      • While the queue is not null
        • For the current size of queue (contains previous level's nodes)
        • Poll the queue. Add the data of the polled node to a sublist.
        • Enqueue the polled node's children (first left then right children) to queue

    Intuition

    In each iteration of the outer while loop, we first check the current size of the queue (the size would give us the number of nodes added at the previous level. For eg, in the first iteration, the size of the queue would be 1 as only root has been added).

    We then iterate till the size of the queue. This way, we remove the nodes from the queue from the previous level (as we are iterating till the size of the queue before we enqueued the current level's nodes and polling the queue) and add the current level's nodes.

    Java

    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
    
            if(root == null) {
                return result;
            }
    
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
    
            while(!queue.isEmpty()) {
                List<Integer> levelNodes = new ArrayList<>();
                Integer currentQueueSize = queue.size();
    
                for(int i = 0; i < currentQueueSize ; i++) {
                    TreeNode tempNode = queue.poll();
                    levelNodes.add(tempNode.val);
    
                    if(tempNode.left != null) {
                        queue.offer(tempNode.left);
                    }
    
                    if(tempNode.right != null) {
                        queue.offer(tempNode.right);
                    }
                }
    
                result.add(levelNodes);
            }
            return result;
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n) n being number of nodes in the tree

    • Space complexity : O(w) w being the max width of the tree


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.