Binary Tree Traversal - Level Order

Problem

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

Examples

Example 1:

Given binary tree {3, 9, 20, #, #, 15, 7},

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

There are multiple variants possible for Level Order Traversal.

Solution

Method 1 - Iterative BFS Using Queue 🏆

Here is the logic:

Q.add(root)
while Q is NOT EMPTY
  T <- Q.remove
  print T.data
  if T.left
     Q.add(T.left)
  if T.right
     Q.add(T.right)

Hence the running time would be O(N).

Code:

public static List<Integer> levelOrderTraversal(TreeNode root) {
	Queue<TreeNode> queue = new LinkedList<>();
	queue.add(root);
	List<Integer> list = new LinkedList<>();


	while (!queue.isEmpty()) {
		TreeNode node = queue.peek();
		if (node != null) {
			list.add(node.data);
			queue.remove();

			if (node.left != null)
				queue.add(node.left);

			if (node.right != null)
				queue.add(node.right);
		}

	}
	return list;
}

Method 2 - Using 2 Stacks

Here is the logic:

S1, S2 ;
S1.push(root)
while S1 OR S2 is not empty
   while S1 is not empty
       T <- S1.pop
       if T.left  
          print T.left.data
          S2.push(T.left)
       if T.right
          print T.right.data
          S2.push(T.right)
  while S2 is not empty
     S1.push(S2.pop)

Complexity

The level order traversal algorithm using two stacks exhibits a time complexity dependent on the tree’s height, particularly in skewed cases.

Nested Loops: The algorithm employs two nested loops. The outer loop iterates for O(H) times, where H represents the tree’s height. This loop ensures each level is visited.
Inner Loop and Level Iteration: Within each outer loop iteration, an inner loop processes the nodes in the current level. This inner loop’s execution time scales with the number of nodes in that level. In a balanced tree, the number of nodes at each level roughly doubles compared to the previous level, leading to an exponential growth of O(2^K) for the inner loop, where K represents the current level.

Combined Complexity:

Combining the outer and inner loops’ contributions, the initial expression for runtime becomes O(H) * O(2^K) + O(2^K). However, the constant term O(2^K) within the first summation can be ignored as it grows slower than the exponential term. Simplifying further, we get O(2^K) * (O(H) + 1), which essentially translates to O(H) * O(2^K).

Problem#

Examples#

Solution#

Method 1 - Iterative BFS Using Queue 🏆#

Method 2 - Using 2 Stacks#

Complexity#