The following article is a solution that aims to solve mostly the LeetCode problem number 102 Binary Tree Level Order Traversal.
Introduction
This is a medium LeetCode problem, under number 102 – Binary Tree Level Order Traversal. The problem definition goes like this:
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).
At first, LeetCode gives us an excellent example of what the problem requires to solve.
1
/ \
21 22
/ \
31 32
As we move on the levels of the Binary Tree, we need to add all elements on that level to the list. The result will then consist of all the element lists from all the levels of the Binary Tree.
Output:
[[1],[21,22],[31,32]]Constrains
There are two constraints for this LeetCode problem:
- The number of nodes in the tree is in the range [0, 2000].
- -1000 <= Node.val <= 1000
While the sheer value of the node is not the problem (second constraint), the range condition for the number of nodes in the tree is (first constraint). As you can see, the lower range is 0. And zero means that we can get a null reference (rather null-pointer) as input for our algorithmic solution. Keep in mind this edge case when trying to solve this LeetCode problem.
Binary Tree Level Order Traversal Solution solution
If you think about it, the solution to this problem is relatively straightforward. So, let’s try to solve this problem decoratively, and you will see how easy it is to solve this problem.
We need two lists, one for overall results and one for partial sub-level results. We will collect sub-level results into overall results.
List subResults = new ArrayList<>();
List> results = new ArrayList<>(); We will also need two queues, one for the current iteration and the second for collecting the next Tree level elements.
Queue queue = new LinkedList<>();
Queue nextLevelQueue = new LinkedList<>(); We need to start the algorithmic engine by padding the root into the current iteration queue. After the first root element is placed into the current iteration queue, we can iterate through the current iteration queue until it is empty and check all nodes for the next level tree nodes. Then, subsequent level tree nodes will be placed into the next level queue.
Queue queue = new LinkedList<>();
List subResults = new ArrayList<>();
queue.add(root);
Queue nextLevelQueue = new LinkedList<>();
List> results = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
if (treeNode.left != null) {
nextLevelQueue.add(treeNode.left);
}
if (treeNode.right != null) {
nextLevelQueue.add(treeNode.right);
}
subResults.add(treeNode.val);
}
return results; At the end of the iteration, for each current level node, we need to check if the current level queue is empty. If the queue is empty, we need to appropriately exchange values and clean up current level temporal data storage.
if (queue.isEmpty()) {
queue.addAll(nextLevelQueue);
nextLevelQueue = new LinkedList<>();
results.add(subResults);
subResults = new ArrayList<>();
}In the end, the whole algorithm will be looking like this:
public class Solution {
public static List> levelOrder(TreeNode root) {
Queue queue = new LinkedList<>();
List subResults = new ArrayList<>();
queue.add(root);
Queue nextLevelQueue = new LinkedList<>();
List> results = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
if (treeNode.left != null) {
nextLevelQueue.add(treeNode.left);
}
if (treeNode.right != null) {
nextLevelQueue.add(treeNode.right);
}
subResults.add(treeNode.val);
if (queue.isEmpty()) {
queue.addAll(nextLevelQueue);
nextLevelQueue = new LinkedList<>();
results.add(subResults);
subResults = new ArrayList<>();
}
}
return results;
}
} Now, we should look at our solution and solve it for any edge case we can think of. Does the current solution work for all edge cases?
Do you remember when we were instantly suspicious about LeetCode problem constraints and the possibility of null-pointer on method input? Let’s handle the root null case now:
public class Solution {
public static List> levelOrder(TreeNode root) {
List> results = new ArrayList<>();
if (root == null) {
return results;
}
Queue queue = new LinkedList<>();
List subResults = new ArrayList<>();
queue.add(root);
Queue nextLevelQueue = new LinkedList<>();
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
if (treeNode.left != null) {
nextLevelQueue.add(treeNode.left);
}
if (treeNode.right != null) {
nextLevelQueue.add(treeNode.right);
}
subResults.add(treeNode.val);
if (queue.isEmpty()) {
queue.addAll(nextLevelQueue);
nextLevelQueue = new LinkedList<>();
results.add(subResults);
subResults = new ArrayList<>();
}
}
return results;
}
} Is this a good solution? Yes and no. One can argue that our solution is an unclever – brute-force solution. You managed to solve the problem. But you used too many resources doing it. Are two queues necessary? Do we need to reference a new element every iteration?
In reality, there is a better way to iterate through the tree and search for its breath. And for any successful coding interview, for any qualified interview candidate, the candidate should know better than writing algorithm in a brute-force way. Especially in the case of this LeetCode problem. Binary Tree Level Order Traversal problem is an excellent exercise for the Breath-First Search candidate knowledge demonstration.
Let’s go and optimize the existing solution.
public class Solution {
public List> levelOrder(TreeNode root) {
List> results = new ArrayList<>();
if(root == null) {
return results;
}
Queue queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int queueSize = queue.size();
List subResults = new LinkedList<>();
// This will loop n-times based on the size of queue in current moment
for (int i = 0; i < queueSize; i++) {
TreeNode treeNode = queue.remove();
if(treeNode.left != null) {
queue.add(treeNode.left);
}
if(treeNode.right != null) {
queue.add(treeNode.right);
}
subResults.add(treeNode.val);
}
results.add(subResults);
}
return results;
}
} As you can see, we managed to eliminate one entire queue by checking queue size when iterating through the current level of tree breath.
While this algorithm is excellent, we still introduce a new reference on the variable for every iteration; and we did not fully utilize the full potential of Queue data structure. It is possible to improve even this even differently.
public class Solution {
public List> levelOrder(TreeNode root) {
List> results = new ArrayList<>();
if(root == null) {
return results;
}
Queue queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int queueSize = queue.size();
List subResults = new LinkedList<>();
// This will loop n-times based on the size of queue in current moment
for (int i = 0; i < queueSize; i++) {
if(queue.peek().left != null) {
queue.offer(queue.peek().left);
}
if(queue.peek().right != null) {
queue.offer(queue.peek().right);
}
subResults.add(queue.poll().val);
}
results.add(subResults);
}
return results;
}
} Now the solution does not create a reference on a new element every iteration.
Rewriting this solution for this LeetCode problem several times is a good exercise for using Queue methods and knowledge of the Breadth-First Search algorithm.
Note to remember: Learn following algorithmic structure by heart. It is a signal of good knowledge of data structures.
Tests
All three tests provided by LeetCode are sufficient to cover the most important cases:
public class TestCases {
private static final boolean TRUE = true;
@Test
public void testLeetcodeBasicExamples() {
// Example 1
// root = [3,9,20,null,null,15,7]
TreeNode input = new TreeNode(3,
new TreeNode(9, null, null),
new TreeNode(20,
new TreeNode(15, null, null),
new TreeNode(7, null, null)));
List> result = Solution.levelOrder(input);
Assert.assertEquals(List.of(3), result.get(0));
Assert.assertEquals(List.of(9,20), result.get(1));
Assert.assertEquals(List.of(15,7), result.get(2));
// Example 2
// root = [1]
input = new TreeNode(1, null, null);
result = Solution.levelOrder(input);
Assert.assertEquals(List.of(1), result.get(0));
// Example 3
// root = []
input = new TreeNode(1, null, null);
result = Solution.levelOrder(input);
Assert.assertEquals(TRUE, result.isEmpty());
}
} This article went through several stages of solving has LeetCode Binary Tree Level Order Traversal problem. First, we designed a rough brute-force leaky solution which we trough out the article turned to a fine-grained, edge-case handling solution that fully utilized Queue methods.
This LeetCode Binary Tree Level Order Traversal problem is an outstanding problem to exercise Breath-First Search and Java Queue as data structure.
Keep in mind edge conditions. As we have seen, there was a sneaky constraint that could be lethal during your coding interview. Always start with defining and realizing problem constraints; keep them somewhere on the edge of your board but always visible. Test your solution for edge cases before submission.
Do you know other ways how to solve this problem? Did you find a mistake in our solution? Or have you found a similar question on other platforms? Let us know in the comment to adjust the description, and your contribution will help others better solve this problem.