Leetcode 75: 102. Binary Tree Level Order Traversal

Question:

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).

Example 1:

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

Example 2:

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

Example 3:

Input: root = [] Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000

Solution: Using a recursive approach

  • One way is to have a function to print a given level of a binary tree.
  • Using the height utility function, we can iterate over all the available levels of a tree, and then call the above returnCurrentLevel function, and keep adding the list from every level to our resultant level.
  • Obviously, this will involve visiting nodes multiple times, and will be slow.
  • This is a O(n^2) approach.
  • In the returnCurrentLevel function,
    • If the root is null, then return.
    • Once the original level (provided as an input) becomes, print the node. Because that's what will happen, as we keep decrementing the level going from level 1 to n.
    • If the current level > 1,
      • call the returnCurrentLevel function on both root.left, and root.right nodes and at the same time, decrement the level by 1.

Code:


class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> res = new ArrayList<>();

        int height = height(root);
        for(int i = 1; i <= height; i++){

            List<Integer> temp = new ArrayList<>();
            returnCurrentLevel(root, i, temp);
            res.add(temp);

        }

        return res;
    }

    static int height(TreeNode root){

        if(root == null) return 0;

        return 1 + Math.max(height(root.left), height(root.right));

    }

    static void returnCurrentLevel(TreeNode root, int level, List<Integer> temp){

        if(root == null) return;

        if(level == 1) {

            temp.add(root.val);
            return;

        } else if(level > 1){

            returnCurrentLevel(root.left, level - 1, temp);
            returnCurrentLevel(root.right, level - 1, temp);
        }

    }
}

Complexity:

  • Time: O(N^2) in worst case.
  • Space: O(N) in worst case. (for skewed tree). For balanced tree, call stack uses O(logN) space.

Solution: Using Queue

  • Initialize a queue of TreeNodes.
  • 'Offer' the root node.
  • Now, while the queue is not empty, do the following:
    • Get the count of the elements in the queue. This gives us the number of elements at the current level of Binary Tree.
    • Initialize a new temp ArrayList.
    • Loop over the count number of elements in the queue. (i = 0 to count - 1)
      • Keep adding the left, and right child of each of the above elements in the queue.
      • Once that is done, add the value of the ith node to the temp ArrayList, and poll the ith node.
    • Add the temp ArrayList to the wrapperList (res). This count list of lists of elements of every level.
  • This is the O(n) approach since we visit every node only once.
  • Space: We will storing all the nodes atleast once in the queue. So, it's proportional to the number of nodes in the tree.

Code:


class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){

            int count = queue.size();

            List<Integer> temp = new ArrayList<>();

            for(int i = 0; i < count; i++){

                if(queue.peek().left != null) queue.offer(queue.peek().left);
                if(queue.peek().right != null) queue.offer(queue.peek().right);
                temp.add(queue.poll().val);

            }

            res.add(temp);                     

        }

        return res;
    }

}

Complexity:

  • Time: O(N)
  • Space: O(N)