Problem statement:
Level order traversal for binary tree.
Example:
Logic:
Basic idea behind level order traversal is explained in previous post on same topic. However, instead of using extra TreeNode as marker node to mark end of level, we will use ‘prevCount’ variable which will keep count for how many nodes we need to check if they have any child node in next level. For eg. for level 0, prevCount will be 1. So, we need to check for 1 node if there are any children. Number of children will be stored in ‘curCount’ variable. When prevCount is equal to 0, that means we finished checking for children of all the nodes at current level. Now prevCount will be curCount as for next level we need to check for curCount number of nodes. This idea will be more clear with below detail example for the above diagram.
- At start prevCount = 1,curCount = 0, and queue contains: <50>. We will repeat below steps while queue is not empty.
- Dequeue 5o, prevCount = 0, if left child of 50 present,curCount = 1 enqueue <35>, if right child of 50 present, curCount increment, curCount = 2, enqueue 57, queue <35,57>
- Now, prevCount is 0 means all nodes of current levels are traversed, so prevCount = nextLevel, in this example prevCount = 2 and curCount is updated to 0.
- Repeat step 2 and 3 till queue is not empty. prevCount =0, indicates that we finished traversing curCount and assigning curCount count to prevCount indicates how many nodes need to be traversed in next level.
Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new LinkedList<List<Integer>>(); List<Integer> levels = new LinkedList<Integer>(); Queue<TreeNode> q = new LinkedList<TreeNode>(); if(root == null) return result; q.add(root); int preCount = 1; int curCount = 0; while(!q.isEmpty()) { TreeNode currentNode = q.remove(); preCount--; levels.add(currentNode.val); if(currentNode.left != null) { q.add(currentNode.left); curCount++; } if(currentNode.right != null) { q.add(currentNode.right); curCount++; } if(preCount == 0) { result.add(new LinkedList<Integer>(levels)); levels.clear(); preCount = curCount; curCount = 0; } } return result; } |
Note:
This approach can be extended to perform level order traversal for k-ary tree. We can similarly keep track of number of nodes at parent level and number of nodes need to be traversed in next level.