Problem

Given a binary tree, print it in vertical order sum

Examples

Example 1:

1
2
3
4
5
6

Input:
root = [1,2,3,4,5,6,7]
Output:
 [4, 2, 12, 3, 7]

Explanation: You can see in the example above, [4], [2], [12], [3], [7] are the vertical order sum of the given binary tree.

Solution

Do the inorder traversal. Take a variable called level, when ever you fo left, do level++ AND when ever you go right do level - -. We dont mean level as height but horizontal differential HD.

With step above we have separated out the levels vertically.

Method 1 - Using Hashmap

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

public List<Integer> verticalOrderSum(TreeNode root) {
	List<Integer> ans = new LinkedList<>();
	// base case
	if (root == null) {
		return ans;
	}

	Map<Integer, Integer> map = new HashMap<Integer, Integer>();

	helper(root, 0, map);

	if (map != null) {
		ans.addAll(map.entrySet());
	}
}

private void helper(TreeNode root, int hd,
	Map<Integer, Integer> map) {

	if (root == null) {
		return;
	}

	helper(root.left(), hd - 1, map);

	int prevSum = map.getOrDefault(hd);
	map.put(hd, prevSum + root.key());

	// Store the values in hM for right subtree
	helper(root.right(), hd + 1, map);
}

Method 2 - Using Doubly Link List

Here is the logic:

  1. Start with the root node and empty double list listNode
  2. Add the value of the rootNode to the current listNode
  3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively.
  4. Similarly for right node, pass listNode.right and root.right

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class DLLNode {
	int val;
	DLLNode next;
	DLLNode prev;
	public DLLNode(int val) {
		this.val = val;
	}
}


public List<Integer> verticalOrderSum(TreeNode root) {
	List<Integer> ans = new LinkedList<>();
	if (root == null) {
		return ans;
	}
	DLLNode dllNode = new DLLNode(root.val);
	helper(root.left, dllNode.next);
	helper(root.right, dllNode.prev);


	DLLNode curr = dll;
	// reach start of list
	while (curr.prev != null) {
		curr = curr.prev;
	}

	// now iterate and add the answers
	while (curr.next != null) {
		ans.add(curr.val);
	}
	return ans;
}


private void helper(TreeNode root, DLLNode dllNode) {
	if (root == null) {
		return;
	}

	if (dllNode == null) {
		dllNode = new DLLNode(root.val); 
	} else {
		dllNode.val += root.val;
	}

	helper(root.left, dllNode.prev);
	helper(root.right, dllNode.next);
}