Algorithm {Binary Tree Level Order Traversal II}

Binary Tree Level Order Traversal

Today we will work on the tree traversal task – Binary Tree Level Order Traversal II. We can see that task is pointed as second (II) it means not simple/classic level order traversal, so, let’s read task description:

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

So, as expected task is not usual classic traversal, we should print tree from bottom to top.

Stop and think what do we have and what we should to do.

We have classic binary tree. And we should traverse this tree level by level and after that create result list from end level to first. So, during traversing we can store level by level data until last and after that read from top level by level and put to result list. What data structure has that behaviour? Yes, Stack (LIFO).

So, we have analysed problem let’s implement it:

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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52	
public class BinaryTreeLevelOrderTraversalII {
public List<List<Integer>> levelOrderBottom(final TreeNode root) {
 
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null)
return result;
 
Stack<List<TreeNode>> stack = new Stack<List<TreeNode>>();
levelOrderTraversal(root, stack);
fillResult(result, stack);
return result;
}
 
private void fillResult(List<List<Integer>> result, Stack<List<TreeNode>> stack) {
while (!stack.isEmpty()) {
List<Integer> list = convertToIntegerList(stack.pop());
result.add(list);
}
}
 
private void levelOrderTraversal(TreeNode root, Stack<List<TreeNode>> stack) {
Queue<TreeNode> current = new LinkedList<TreeNode>();
Queue<TreeNode> next = new LinkedList<TreeNode>();
current.offer(root);
stack.push(new ArrayList<TreeNode>(current));
 
while (!current.isEmpty()) {
TreeNode node = current.poll();
if (node.left != null) {
next.offer(node.left);
}
if (node.right != null) {
next.offer(node.right);
}
if (current.isEmpty()) {
if (!next.isEmpty()) {
stack.push(new ArrayList<TreeNode>(next));
}
current = next;
next = new LinkedList<TreeNode>();
}
}
}
 
private List<Integer> convertToIntegerList(List<TreeNode> nodes) {
List<Integer> result = new ArrayList<Integer>();
for (TreeNode node : nodes) {
result.add(node.val);
}
return result;
}
}

public class BinaryTreeLevelOrderTraversalII {
public List<List<Integer>> levelOrderBottom(final TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null)
return result;
Stack<List<TreeNode>> stack = new Stack<List<TreeNode>>();
levelOrderTraversal(root, stack);
fillResult(result, stack);
return result;
}
private void fillResult(List<List<Integer>> result, Stack<List<TreeNode>> stack) {
while (!stack.isEmpty()) {
List<Integer> list = convertToIntegerList(stack.pop());
result.add(list);
}
}
private void levelOrderTraversal(TreeNode root, Stack<List<TreeNode>> stack) {
Queue<TreeNode> current = new LinkedList<TreeNode>();
Queue<TreeNode> next = new LinkedList<TreeNode>();
current.offer(root);
stack.push(new ArrayList<TreeNode>(current));
while (!current.isEmpty()) {
TreeNode node = current.poll();
if (node.left != null) {
next.offer(node.left);
}
if (node.right != null) {
next.offer(node.right);
}
if (current.isEmpty()) {
if (!next.isEmpty()) {
stack.push(new ArrayList<TreeNode>(next));
}
current = next;
next = new LinkedList<TreeNode>();
}
}
}
private List<Integer> convertToIntegerList(List<TreeNode> nodes) {
List<Integer> result = new ArrayList<Integer>();
for (TreeNode node : nodes) {
result.add(node.val);
}
return result;
}
}