Posts Vertical Order Traversal - Binary Tree
Post
Cancel

Vertical Order Traversal - Binary Tree

PROBLEM DESCRIPTION

Given a binary tree, return a 2-D array with vertical order traversal of it.

SOLUTION

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
53
54
55
56
57
58
59
60
61
62
63
public class Solution {
    
    public ArrayList<ArrayList<Integer>> verticalOrderTraversal(TreeNode A) {

        TreeNode root = A;

        if(root == null) return new ArrayList<ArrayList<Integer>>();
        
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(root, 0));
        
        Map<Integer, ArrayList<Integer>> map = new HashMap<>();
        
        int minLevel=0;
        int maxLevel=0;
        
        while(!q.isEmpty()){
            
            Pair p = q.remove();
            
            TreeNode node = p.node;
            int level = p.level;
            
            if(!map.containsKey(level)){
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(node.val);
                map.put(level, list);
            }else{
                map.get(level).add(node.val);
            }
            
            if(node.left != null){
                q.add(new Pair(node.left, level-1));    
                minLevel = Math.min(minLevel, level-1);
            }
            if(node.right != null){
                q.add(new Pair(node.right, level+1));    
                maxLevel = Math.max(maxLevel, level+1);
            }
            
        }
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
            
            for(int i=minLevel; i<=maxLevel; i++){
                res.add(map.get(i));
            }
            
            return res;
        
    }

}

class Pair{
    TreeNode node;
    int level;
    public Pair(TreeNode node, int level){
        this.node = node;
        this.level = level;
    }
}

This post is licensed under CC BY 4.0 by the author.