Solution: Binary Tree Level Order Traversal

Let's solve the Binary Tree Level Order Traversal problem using the Tree Breadth-first Search pattern.

We'll cover the following

Statement

Given the root of a binary tree, display the values of its nodes while performing a level order traversal. Return the node values for all levels in a string separated by the character :. If the tree is empty, i.e., the number of nodes is 00, then return “None” as the output.

Constraints:

  • The number of nodes in the tree is in the range [0,500][0, 500].

  • −103≤-10^3 \leq Node.data ≤103\leq 10^3

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach would be to first calculate the height of the tree and then recursively traverse it, level by level. The printing function would be called for every level in the range [1,height][1, height].

In the case of a skewed tree, the time complexity for this approach would be O(n2)O(n^2), where nn is the number of nodes. The space complexity is O(n)O(n).

Optimized approach using tree breadth-first search

We can traverse a binary tree using the depth or breadth-first search pattern. The fundamental characteristic of the depth-first search pattern is that it travels as far as possible along each tree branch before exploring the others.

However, since we are asked to print all nodes at the same hierarchical level, this problem naturally falls under the tree breadth-first search pattern. It starts searching at the root node and moves down level by level, exploring adjacent nodes at level k+1k + 1. We’ll print all the nodes at each level and then move to the next level.

Solution 1

The essence of the algorithm to perform level-order traversal of a binary tree involves using two queues to process nodes level by level, similar to the breadth-first search (BFS) approach. One queue is used to store nodes of the current level, and the other is used to store the nodes of the next level. Starting with the root node in the current queue, each node is dequeued, its value is processed, and its children are added to the next queue. Once all nodes in the current queue are processed, the roles of the two queues are swapped, and the process continues until all levels are traversed.

We can use two queues to solve this problem:

  • A current queue
  • A next queue

The slides below illustrate how the algorithm runs:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

  • First, we’ll declare an array of two queues. This step will help us swap values between our two queues later.

  • We then declare and point currentQueue to the 0th0^{th} index and nextQueue to the 1st1^{st} index of the queues array.

  • We’ll start by pushing the root node to currentQueue and setting the tree level to zero.

Solution.java
BinaryTree.java
TreeNode.java
class Solution {
    public static void printQueue(Queue<TreeNode<Integer>> copy){      
        TreeNode<Integer> node=null;    
        Iterator<TreeNode<Integer>> through = copy.iterator() ;
        while(through.hasNext() ) {
            node = through.next();
            System.out.print("["+ node.data+ "]") ;
        }
        System.out.println() ;
        
    }
    
    public static void levelOrderTraversal(TreeNode<Integer> root) {
        // We print null if the root is null
        if (root == null) {
            System.out.print("null");
        } else {
            System.out.println("\n\tInitializing the queues");
            // Declaring an array of two queues
            ArrayList<Queue<TreeNode<Integer>>> queues = new ArrayList<Queue<TreeNode<Integer>>>();
            queues.add(new ArrayDeque<TreeNode<Integer>>());
            queues.add(new ArrayDeque<TreeNode<Integer>>());
            System.out.println("\t\tqueues array: " + queues);
            // Initializing the current and next queues
            Queue<TreeNode<Integer>> currentQueue = queues.get(0);
            Queue<TreeNode<Integer>> nextQueue = queues.get(1);
            System.out.println("\t\tCurrent queue: " + currentQueue);
            System.out.println("\t\tNext queue: " + nextQueue);
            // Enqueuing the root node into the current queue and setting
            // level to zero
            System.out.println("\t\tEnqueuing the root node into the current queue");
            currentQueue.add(root);
            System.out.print("\t\t\tUpdated current queue: ");
            printQueue(currentQueue);
            int levelNumber = 0;
            System.out.println("\t\t\tLevel number: " + levelNumber);
        }
    }
    
	public static void main(String[] argv) {
		 List<TreeNode<Integer>> testCasesRoots = new ArrayList<>();
        List<TreeNode<Integer>> input1 = Arrays.asList(
                new TreeNode<>(100),
                new TreeNode<>(50),
                new TreeNode<>(200),
                new TreeNode<>(25),
                new TreeNode<>(75),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree1 = new BinaryTree<>(input1);
        testCasesRoots.add(tree1.root);
        List<TreeNode<Integer>> input2 = Arrays.asList(
                new TreeNode<>(25),
                new TreeNode<>(50),
                null,
                new TreeNode<>(100),
                new TreeNode<>(200),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree2 = new BinaryTree<>(input2);
        testCasesRoots.add(tree2.root);
        List<TreeNode<Integer>> input3 = Arrays.asList(
                new TreeNode<>(350),
                null,
                new TreeNode<>(100),
                null,
                new TreeNode<>(50),
                new TreeNode<>(25)
        );
        BinaryTree<Integer> tree3 = new BinaryTree<>(input3);
        testCasesRoots.add(tree3.root);
        BinaryTree<Integer> tree4 = new BinaryTree<>(Arrays.asList(new TreeNode<>(100)));
        testCasesRoots.add(tree4.root);
        testCasesRoots.add(null);
        for (int i = 0; i < testCasesRoots.size(); i++) {
            if (i > 0) {
                System.out.println("\n");
            }
            System.out.println(i + 1 + ".\tBinary Tree");
            Print.displayTree(testCasesRoots.get(i));
            System.out.print("\n\tLevel order traversal: ");
            levelOrderTraversal(testCasesRoots.get(i));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Pushing the root node

We’ll carry out the following operations until currentQueue is empty:

  • Dequeue the first element of currentQueue.

  • Enqueue its children to nextQueue.

  • Store the dequeued node in result.

Solution.java
BinaryTree.java
TreeNode.java
class Solution {
    
    public static String printQueue(Queue<TreeNode<Integer>> copy) {
        if (copy != null && !copy.isEmpty()) {
            StringBuilder output = new StringBuilder("[");
            for (TreeNode<Integer> through : copy) {
                output.append(through.data).append(", ");
            }
            output.delete(output.length() - 2, output.length());
            output.append("]");
            return output.toString();
        }
        return "[]";
    }
    public static String levelOrderTraversal(TreeNode<Integer> root) {
        StringBuilder result = new StringBuilder();
        // Print None if the root doesn't exist
        if (root == null) {
            System.out.print("None");
        } else {
            System.out.println("\n\tInitializing the queues");
            // Declaring an array of two queues
            ArrayList<Queue<TreeNode<Integer>>> queues = new ArrayList<Queue<TreeNode<Integer>>>();
            queues.add(new ArrayDeque<TreeNode<Integer>>());
            queues.add(new ArrayDeque<TreeNode<Integer>>());
            System.out.println("\t\tqueues array: " + queues);
            // Initializing the current and next queues
            Queue<TreeNode<Integer>> currentQueue = queues.get(0);
            Queue<TreeNode<Integer>> nextQueue = queues.get(1);
            System.out.println("\t\tCurrent queue: " + currentQueue);
            System.out.println("\t\tNext queue: " + nextQueue);
            // Enqueuing the root node into the current queue and setting
            // level to zero
            System.out.println("\t\tEnqueuing the root node into the current queue");
            currentQueue.add(root);
            System.out.print("\t\t\tUpdated current queue: " + printQueue(currentQueue));
            int levelNumber = 0;
            System.out.println("\n\t\t\tLevel number: " + levelNumber);
            System.out.println("\n\tIterating the current queue");
            int n = 0;
            while (!currentQueue.isEmpty()) {
                System.out.println("\t\tLoop iteration " + n);
                n += 1;
                // Dequeuing and printing the first element of queue
                System.out.print("\t\t\tDequeuing from the current queue: " + printQueue(currentQueue));
                TreeNode<Integer> temp = currentQueue.poll();
                System.out.println(" ⟶ " + printQueue(currentQueue));
                System.out.println("\t\t\t\tPopped node: " + temp.data);
                result.append(String.valueOf(temp.data));
                System.out.println("\t\t\t\tAppending the popped node to the results string: " + result);
                // Adding dequeued node's children to the next queue
                System.out.println("\t\t\tAdding " + temp.data + "'s children to the next queue");
                if (temp.left != null) {
                    nextQueue.add(temp.left);
                    System.out.println("\t\t\t\tEnqueuing the left child, "+ temp.left.data);
                    System.out.print("\t\t\t\t\tNext queue: " + printQueue(nextQueue));
                }
                if (temp.right != null) {
                    nextQueue.add(temp.right);
                    System.out.println("\n\t\t\t\tEnqueuing the right child, "+ temp.right.data);
                    System.out.print("\t\t\t\t\tNext queue: " + printQueue(nextQueue));
                }
            }
        }
        return result.toString();
    }
    
	public static void main(String[] argv) {
		 List<TreeNode<Integer>> testCasesRoots = new ArrayList<>();
        List<TreeNode<Integer>> input1 = Arrays.asList(
                new TreeNode<>(100),
                new TreeNode<>(50),
                new TreeNode<>(200),
                new TreeNode<>(25),
                new TreeNode<>(75),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree1 = new BinaryTree<>(input1);
        testCasesRoots.add(tree1.root);
        List<TreeNode<Integer>> input2 = Arrays.asList(
                new TreeNode<>(25),
                new TreeNode<>(50),
                null,
                new TreeNode<>(100),
                new TreeNode<>(200),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree2 = new BinaryTree<>(input2);
        testCasesRoots.add(tree2.root);
        List<TreeNode<Integer>> input3 = Arrays.asList(
                new TreeNode<>(350),
                null,
                new TreeNode<>(100),
                null,
                new TreeNode<>(50),
                new TreeNode<>(25)
        );
        BinaryTree<Integer> tree3 = new BinaryTree<>(input3);
        testCasesRoots.add(tree3.root);
        BinaryTree<Integer> tree4 = new BinaryTree<>(Arrays.asList(new TreeNode<>(100)));
        testCasesRoots.add(tree4.root);
        testCasesRoots.add(null);
        for (int i = 0; i < testCasesRoots.size(); i++) {
            if (i > 0) {
                System.out.println("\n");
            }
            System.out.println(i + 1 + ".\tBinary Tree");
            Print.displayTree(testCasesRoots.get(i));
            System.out.print("\n\tLevel order traversal: ");
            System.out.println(levelOrderTraversal(testCasesRoots.get(i)) + "\n");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Dequeue operation

  • The loop in the code above runs once, since we only have one node in currentQueue. To ensure all the tree nodes are visited, we’ll swap currentQueue and nextQueue once the former becomes empty.

  • We’ll swap currentQueue with nextQueue and increment levelNumber by 11. Since we’re moving to the next level, we’ll also append : to result.

  • We terminate the loop if currentQueue is still empty and return the result.

Solution.java
BinaryTree.java
TreeNode.java
class Solution {
    public static String printQueue(Queue<TreeNode<Integer>> copy) {
        if (copy != null && !copy.isEmpty()) {
            StringBuilder output = new StringBuilder("[");
            for (TreeNode<Integer> through : copy) {
                output.append(through.data).append(", ");
            }
            output.delete(output.length() - 2, output.length());
            output.append("]");
            return output.toString();
        }
        return "[]";
    }
    public static String levelOrderTraversal(TreeNode<Integer> root) {
        // We print null if the root is null
        StringBuilder result = new StringBuilder();
        if (root == null) {
            System.out.println("None");
            return "None";
        } else {
            System.out.println("\n\tInitializing the queues");
            // Declaring an array of two queues
            ArrayList<Queue<TreeNode<Integer>>> queues = new ArrayList<Queue<TreeNode<Integer>>>();
            queues.add(new ArrayDeque<TreeNode<Integer>>());
            queues.add(new ArrayDeque<TreeNode<Integer>>());
            System.out.println("\t\tqueues array: " + queues);
            // Initializing the current and next queues
            Queue<TreeNode<Integer>> currentQueue = queues.get(0);
            Queue<TreeNode<Integer>> nextQueue = queues.get(1);
            System.out.println("\t\tCurrent queue: " + currentQueue);
            System.out.println("\t\tNext queue: " + nextQueue);
            // Enqueuing the root node into the current queue and setting
            // level to zero
            System.out.println("\t\tEnqueuing the root node into the current queue");
            currentQueue.add(root);
            System.out.print("\t\t\tUpdated current queue: " + printQueue(currentQueue));
            int levelNumber = 0;
            System.out.println("\n\t\t\tLevel number: " + levelNumber);
            System.out.println("\n\tIterating the current queue");
            int n = 0;
            while (!currentQueue.isEmpty()) {
                System.out.println("\n\t\tLoop iteration " + n);
                n += 1;
                // Dequeuing and printing the first element of queue
                System.out.print("\t\t\tDequeuing from the current queue: " + printQueue(currentQueue));
                TreeNode<Integer> temp = currentQueue.poll();
                System.out.println(" ⟶ " + printQueue(currentQueue));
                System.out.println("\t\t\t\tPopped node: " + temp.data);
                result.append(String.valueOf(temp.data));
                System.out.println("\t\t\t\tAppending the popped node to the results string: " + result);
                // Adding dequeued node's children to the next queue
                System.out.println("\t\t\tAdding " + temp.data + "'s children to the next queue");
                
                if (temp.left != null) {
                    nextQueue.add(temp.left);
                    System.out.println("\t\t\t\tEnqueuing the left child, " + temp.left.data);
                    System.out.print("\t\t\t\t\tNext queue: " + printQueue(nextQueue));
                }
                if (temp.right != null) {
                    nextQueue.add(temp.right);
                    System.out.println("\n\t\t\t\tEnqueuing the right child, " + temp.right.data);
                    System.out.print("\t\t\t\t\tNext queue: " + printQueue(nextQueue));
                }
                // When the current queue is empty, we increase the level, print a new line
                // and swap the current and next queues
                System.out.print("\n\n\t\t\tCurrent queue: " + printQueue(currentQueue));
                System.out.print("\n\t\t\tNext queue: " + printQueue(nextQueue));
                if (currentQueue.isEmpty()) {
                    System.out.println("\n\t\t\tCurrent queue is empty, swapping the queues");
                    ++levelNumber;
                    if (!nextQueue.isEmpty()) {
                        result = result.append(" : ");
                        System.out.println("\t\t\t\tMoving to the next level, appending a colon to the result string  ⟶ "+ result);
                    }
                    currentQueue = queues.get(levelNumber % 2);
                    nextQueue = queues.get((levelNumber + 1) % 2);
                    System.out.println("\t\t\t\tIncrementing level number: " + (levelNumber - 1) + " ⟶ " + levelNumber);
                    System.out.print("\t\t\t\tCurrent queue after swapping: " + printQueue(currentQueue));
                    System.out.print("\n\t\t\t\tNext queue after swapping: " + printQueue(nextQueue));
                } else {
                    result = result.append(", ");
                }
            }
            System.out.println("\n\n\tLevel order traversal: " + result);
        }
        return result.toString();
    }
    
	public static void main(String[] argv) {
		 List<TreeNode<Integer>> testCasesRoots = new ArrayList<>();
        List<TreeNode<Integer>> input1 = Arrays.asList(
                new TreeNode<>(100),
                new TreeNode<>(50),
                new TreeNode<>(200),
                new TreeNode<>(25),
                new TreeNode<>(75),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree1 = new BinaryTree<>(input1);
        testCasesRoots.add(tree1.root);
        List<TreeNode<Integer>> input2 = Arrays.asList(
                new TreeNode<>(25),
                new TreeNode<>(50),
                null,
                new TreeNode<>(100),
                new TreeNode<>(200),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree2 = new BinaryTree<>(input2);
        testCasesRoots.add(tree2.root);
        List<TreeNode<Integer>> input3 = Arrays.asList(
                new TreeNode<>(350),
                null,
                new TreeNode<>(100),
                null,
                new TreeNode<>(50),
                new TreeNode<>(25)
        );
        BinaryTree<Integer> tree3 = new BinaryTree<>(input3);
        testCasesRoots.add(tree3.root);
        BinaryTree<Integer> tree4 = new BinaryTree<>(Arrays.asList(new TreeNode<>(100)));
        testCasesRoots.add(tree4.root);
        testCasesRoots.add(null);
        for (int i = 0; i < testCasesRoots.size(); i++) {
            if (i > 0) {
                System.out.println("\n");
            }
            System.out.println(i + 1 + ".\tBinary Tree");
            Print.displayTree(testCasesRoots.get(i));
            System.out.print("\n\tLevel order traversal: ");
            System.out.println(levelOrderTraversal(testCasesRoots.get(i)) + "\n");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Binary Tree Level Order Traversal
Just the code

Here’s the complete solution to this problem:

Solution.java
BinaryTree.java
TreeNode.java
class Solution {
    public static String levelOrderTraversal(TreeNode<Integer> root) {
 
        StringBuilder result = new StringBuilder();
        if (root == null) {
            return "None";
        } else {
            ArrayList<Queue<TreeNode<Integer>>> queues = new ArrayList<Queue<TreeNode<Integer>>>();
            queues.add(new ArrayDeque<TreeNode<Integer>>());
            queues.add(new ArrayDeque<TreeNode<Integer>>());
            Queue<TreeNode<Integer>> currentQueue = queues.get(0);
            Queue<TreeNode<Integer>> nextQueue = queues.get(1);
            currentQueue.add(root);
            int levelNumber = 0;
            while (!currentQueue.isEmpty()) {
                TreeNode<Integer> temp = currentQueue.poll();
                result.append(String.valueOf(temp.data));
                
                if (temp.left != null) {
                    nextQueue.add(temp.left);
                }
                if (temp.right != null) {
                    nextQueue.add(temp.right);
                }
                if (currentQueue.isEmpty()) {
                    ++levelNumber;
                    if (!nextQueue.isEmpty()) {
                        result = result.append(" : ");
                    }
                    currentQueue = queues.get(levelNumber % 2);
                    nextQueue = queues.get((levelNumber + 1) % 2);
    
                } else {
                    result = result.append(", ");
                }
            }
        }
        return result.toString();
    }
    
	public static void main(String[] argv) {
		 List<TreeNode<Integer>> testCasesRoots = new ArrayList<>();
        List<TreeNode<Integer>> input1 = Arrays.asList(
                new TreeNode<>(100),
                new TreeNode<>(50),
                new TreeNode<>(200),
                new TreeNode<>(25),
                new TreeNode<>(75),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree1 = new BinaryTree<>(input1);
        testCasesRoots.add(tree1.root);
        List<TreeNode<Integer>> input2 = Arrays.asList(
                new TreeNode<>(25),
                new TreeNode<>(50),
                null,
                new TreeNode<>(100),
                new TreeNode<>(200),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree2 = new BinaryTree<>(input2);
        testCasesRoots.add(tree2.root);
        List<TreeNode<Integer>> input3 = Arrays.asList(
                new TreeNode<>(350),
                null,
                new TreeNode<>(100),
                null,
                new TreeNode<>(50),
                new TreeNode<>(25)
        );
        BinaryTree<Integer> tree3 = new BinaryTree<>(input3);
        testCasesRoots.add(tree3.root);
        BinaryTree<Integer> tree4 = new BinaryTree<>(Arrays.asList(new TreeNode<>(100)));
        testCasesRoots.add(tree4.root);
        testCasesRoots.add(null);
        for (int i = 0; i < testCasesRoots.size(); i++) {
            if (i > 0) {
                System.out.println("\n");
            }
            System.out.println(i + 1 + ".\tBinary Tree");
            Print.displayTree(testCasesRoots.get(i));
            System.out.print("\n\tLevel order traversal: ");
            System.out.println(levelOrderTraversal(testCasesRoots.get(i)) + "\n");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Binary Tree Level Order Traversal
Solution summary

To recap, the solution to this problem can be divided into the following parts:

  1. Use two queues, currentQueue and nextQueue, to keep track of the nodes.

  2. Dequeue nodes from currentQueue and push their children to the nextQueue.

  3. Store the dequeued nodes in result.

  4. If the former queue is empty in step 3, swap the two queues and increment the level number.

  5. Return result once the loop terminates.

Time complexity

The time complexity of this solution is linear, O(n)O(n), where nn is the number of nodes, because every node is visited and printed only once.

Space complexity

The space complexity of this solution is linear, O(n)O(n), since the algorithm instantiates queues that take up space of up to ⌈n/2⌉\lceil{^n/_2}\rceil nodes. This is because the maximum queue size occurs at the level of the leaf nodes of a balanced binary tree.

Solution 2

In the previous solution, we used two queues to keep track of the current level. However, there is an alternative approach to conduct level order traversal on a binary tree using a single deque. It efficiently traverses the tree by processing nodes at each level in a breadth-first manner. By iteratively dequeuing nodes and collecting their data values, it constructs a hierarchical representation of the tree.

The steps for this solution are as follows:

  • Initialize an empty list called result. This list will hold the data of nodes visited in the level order.

  • Check if the tree is empty. If so, we return NULL.

  • Next, create a deque named current_queue to facilitate breath-first traversal.

  • Start by enqueuing the root node to initiate the traversal process.

  • Begin a loop that continues until current_queue is empty.

  • Now, determine the number of nodes at the current level by getting the length of current_queue. Also, initialize an empty list, level_nodes, to store the data of nodes at this level.

  • Next, iterate over the number of nodes in the current level:

    • Dequeue a node (temp) from the front of current_queue.
    • Append the string representation of the node’s data to level_nodes.
    • Enqueue the left and right child of the node(if any) we dequeued in the previous step into current_queue.

  • After processing all nodes at current levels, join the elements in level_nodes into a single string with “,” as a separator.

  • Append this string to the result list, representing one level of the traversal.

  • Once the traversal is complete, join all the level representations stored in the result list into a single string with " : " as the separator.

  • Print the resultant, the string which represents the level-order traversal of the binary tree.

Here’s an example to demonstrate the algorithm mentioned above:

Press + to interact
canvasAnimation-image
1 of 14

Let’s look at the code for this solution below:

Solution.java
BinaryTree.java
TreeNode.java
class Solution {
	
    public static String levelOrderTraversal(TreeNode<Integer> root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return "None";
        }
        Queue<TreeNode<Integer>> current_queue = new ArrayDeque<TreeNode<Integer>>();
        current_queue.add(root);
        while (!current_queue.isEmpty()) {
            int levelSize = current_queue.size();
            List<String> levelNodes = new ArrayList<>();
            for (int i = 0; i < levelSize; i++) {
                TreeNode<Integer> temp = current_queue.poll();
                levelNodes.add(String.valueOf(temp.data));
                if (temp.left != null) {
                    current_queue.add(temp.left);
                }
                if (temp.right != null) {
                    current_queue.add(temp.right);
                }
            }
            result.add(String.join(", ", levelNodes));
        }
        return String.join(" : ", result);
    }
    
	public static void main(String[] argv) {
		 List<TreeNode<Integer>> testCasesRoots = new ArrayList<>();
        List<TreeNode<Integer>> input1 = Arrays.asList(
                new TreeNode<>(100),
                new TreeNode<>(50),
                new TreeNode<>(200),
                new TreeNode<>(25),
                new TreeNode<>(75),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree1 = new BinaryTree<>(input1);
        testCasesRoots.add(tree1.root);
        List<TreeNode<Integer>> input2 = Arrays.asList(
                new TreeNode<>(25),
                new TreeNode<>(50),
                null,
                new TreeNode<>(100),
                new TreeNode<>(200),
                new TreeNode<>(350)
        );
        BinaryTree<Integer> tree2 = new BinaryTree<>(input2);
        testCasesRoots.add(tree2.root);
        List<TreeNode<Integer>> input3 = Arrays.asList(
                new TreeNode<>(350),
                null,
                new TreeNode<>(100),
                null,
                new TreeNode<>(50),
                new TreeNode<>(25)
        );
        BinaryTree<Integer> tree3 = new BinaryTree<>(input3);
        testCasesRoots.add(tree3.root);
        BinaryTree<Integer> tree4 = new BinaryTree<>(Arrays.asList(new TreeNode<>(100)));
        testCasesRoots.add(tree4.root);
        testCasesRoots.add(null);
        for (int i = 0; i < testCasesRoots.size(); i++) {
            if (i > 0) {
                System.out.println("\n");
            }
            System.out.println(i + 1 + ".\tBinary Tree");
            Print.displayTree(testCasesRoots.get(i));
            System.out.print("\n\tLevel order traversal: ");
            System.out.println(levelOrderTraversal(testCasesRoots.get(i)) + "\n");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Binary Tree Level Order Traversal
Solution summary

To recap, the solution to this problem can be divided into the following steps:

  1. Start by initializing an empty result list and a queue, pushing the root onto the queue.
  2. While the queue is not empty, iterate over each level, dequeuing nodes one by one and enqueuing their children.
  3. Collect the data of nodes at each level, join them into strings, and append them to the result list.
  4. Finally, join the level strings with " : " and return the resulting string representing the level-order traversal.
Time complexity

The time complexity of this solution is linear, O(n)O(n), where nn is the number of nodes, because every node is visited and printed only once.

Space complexity

The space complexity of this solution is linear, O(n)O(n), since the algorithm instantiates queues that take up space of up to ⌈n/2⌉\lceil{^n/_2}\rceil nodes. This is because the maximum queue size occurs at the level of the leaf nodes of a balanced binary tree.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.