# Level order traversal wrapping Nodes with a shift index

• The problem with recursive solution is how to keep the order within one shift, since there seems to be no option of level order traversal in doing recursion. I mean case [1,2,3,null,5,6,7,8,null,null,11] will result in one array having [11, 3] with simple recursive implementation. For that I had to try iterative and wrap each node with a shift index. Can any one solve this problem more concisely?

I think the time complexity of the problem is O(N) time & O(N) space. Please point out if I am wrong.

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public class TreeNode1 {
TreeNode node;
int shift;
public TreeNode1 (TreeNode node, int shift) {
this.node = node;
this.shift = shift;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
if (root == null) return new ArrayList<List<Integer>>();
TreeMap<Integer, List<Integer>> tm = new TreeMap<> ();
traverse(tm, root);
List<List<Integer>> results = new ArrayList<>();
for (Integer i : tm.keySet()) results.add(tm.get(i));
return results;
}
public void traverse(TreeMap<Integer, List<Integer>> tm, TreeNode n) {