Table of contents

• Given problem
• Using recursive version
• Using iterative version
• When to use
• Wrapping up

Given problem

Given a binary tree, return the level order traversal of its node’s value.

The output of the above binary tree is:

1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7

Using recursive version

1. First way

   Belows are some steps that we use.

   • The first action we need to do is to calculate the maximum level of the tree.

   • After we had the tree’s maximum level, we will iterate from level 1 to the maximum level, then get all elements of each level.

    public class MaxLevelTraversal {
   
        private static int maxLevel = Integer.MIN_VALUE;
   
        public static List<Integer> levelOrderTraversal(TreeNode root) {
            List<Integer> nodes = new ArrayList<>();
            getMaxLevelTopDown(root, 1);
   
            for (int level = 1; level <= maxLevel; ++level) {
                getNodesInSameLevel(root, level, 1, nodes);
            }
   
            return nodes;
        }
   
        public static void getNodesInSameLevel(TreeNode root, int currentLevel, int level, List<Integer> nodes) {
            if (root == null) {
                return;
            }
   
            if (level == currentLevel) {
                nodes.add(root.val);
            }
   
            getNodesInSameLevel(root.left, currentLevel, level + 1, nodes);
            getNodesInSameLevel(root.right, currentLevel, level + 1, nodes);
        }
   
        private static void getMaxLevelTopDown(TreeNode root, int level) {
            if (root == null) {
                return;
            }
   
            if (root.left == null && root.right == null) {
                maxLevel = Math.max(maxLevel, level);
            }
   
            getMaxLevelTopDown(root.left, level + 1);
            getMaxLevelTopDown(root.right, level + 1);
        }
    }
   

2. Second way

   We will use hashmap to save nodes at each level.

    public class MaxLevelTraversal {
   
        private static Map<Integer, List<Integer>> nodesPerLevel = new HashMap<>();
   
        public static List<Integer> levelOrderTraversalRecursiveVersion1(TreeNode root) {
            recursiveVersion(root, 0);
   
            // convert hash map to list
            if (nodesPerLevel.isEmpty()) {
                return Collections.emptyList();
            }
   
            return nodesPerLevel.values().stream()
                                .flatMap(valNodes -> Stream.of(valNodes.toArray()))
                                                           .map(value -> (Integer) value)
                                .collect(Collectors.toList());
        }
   
        public static void recursiveVersion(TreeNode root, int level) {
            if (root == null) {
                return;
            }
   
            if (nodesPerLevel.size() == level) {
                nodesPerLevel.put(level, new ArrayList<>());
            }
   
            // add the value of current node with the same level
            nodesPerLevel.get(level).add(root.val);
   
            recursiveVersion(root.left, level + 1);
            recursiveVersion(root.right, level + 1);
        }
   

Using iterative version

In this version, we will use Queue to save the children nodes of the current node.

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

Below is the complexity of this way:

• Time complexity: O(n) with n is the number nodes in the tree.
• Space complexity: O(n)

When to use

• When we want to work with the nodes that are in the same level such as applying in the peer-to-peer network, …

Wrapping up

• Understanding about how to use Queue for the Level Order Traversal.

Refer:

https://leetcode.com/problems/binary-tree-level-order-traversal/