Overview

• Level Order Traversal using BFS is an important technique used in a lot of problems.
• This post won't go into the science of BFS or trees, but aims to provide a template needed to solve problems of this theme.
• The same techinque can be extended to N-ary tree with little modification
• This is meant to be a continuosly improving post and I'll keep updating it and add more problems as I progress.
• Collaboration works wonders so I'd encourage anyone reading this post to feel free to contribute for the benefit of the community.

Algorithm:

• Create a queue for BFS with root as the seed value
• Do while the q is not empty
  • For size of q = n, iterate over the q n-times
    • Poll a node from the q and add it to the level.
    • If the node's left child is non-null, then add it to the q. Repeat for right child
  • Add the level to list of levels

Basic Code Template:

T/S: O(n)/O(w), where n = number of nodes in the tree and w = max nodes at any level

public List<List<Integer>> levelOrder(TreeNode root) {
	if (root == null)
		return List.of();

	var lot = new ArrayList<List<Integer>>();
	var q = new ArrayDeque<>(List.of(root));

	while (!q.isEmpty()) {
		var level = new ArrayList<Integer>();

		for (var i = q.size(); i > 0; i--) {
			var node = q.poll();
			level.add(node.val);

			if (node.left != null)
				q.add(node.left);
			if (node.right != null)
				q.add(node.right);
		}
		lot.add(level);
	}
	return lot;
}

Question Bank

• 101. Symmetric Tree
• 102. Binary Tree Level Order Traversal
• 103. Binary Tree Zigzag Level Order Traversal
• 104. Maximum Depth of Binary Tree
• 107. Binary Tree Level Order Traversal II
• 111. Minimum Depth of Binary Tree
• 116. Populating Next Right Pointers in Each Node
• 117. Populating Next Right Pointers in Each Node II
• 199. Binary Tree Right Side View
• 226. Invert Binary Tree
• 297. Serialize and Deserialize Binary Tree
• 429. N-ary Tree Level Order Traversal
• 513. Find Bottom Left Tree Value
• 515. Find Largest Value in Each Tree Row
• 623. Add One Row to Tree
• 637. Average of Levels in Binary Tree
• 662. Maximum Width of Binary Tree
• 847. Shortest Path Visiting All Nodes
• 863. All Nodes Distance K in Binary Tree
• 1161. Maximum Level Sum of a Binary Tree
• 1302. Deepest Leaves Sum
• 1361. Validate Binary Tree Nodes
• 1530. Number of Good Leaf Nodes Pairs
• 1602. Find Nearest Right Node in Binary Tree (P)
• 1609. Even Odd Tree
• 1660. Correct a Binary Tree (P)
• 2385. Amount of Time for Binary Tree to Be Infected
• 2583. Kth Largest Sum in a Binary Tree

Legend: P = Premium

Comments and contributions for improvement are appreciated. Thanks!