Given a binary search tree, sum all the nodes which are at on the same vertical line. For example, in below tree nodes 6 and 5 are on same vertical line.
If we consider root at vertical line 0, the all the nodes in the left side will be on the negative index. Every time we move towards left child, we decrease the index of vertical line and when we move towards the right child,we increase the index of vertical line.
http://www.geeksforgeeks.org/vertical-sum-in-a-given-binary-tree/
Read full article from Algorithms and Me: Binary Search Tree : Vertical sum of nodes
If we consider root at vertical line 0, the all the nodes in the left side will be on the negative index. Every time we move towards left child, we decrease the index of vertical line and when we move towards the right child,we increase the index of vertical line.
http://www.geeksforgeeks.org/vertical-sum-in-a-given-binary-tree/
We need to check the Horizontal Distances from root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the above tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.
We can do inorder traversal of the given Binary Tree. While traversing the tree, we can recursively calculate HDs. We initially pass the horizontal distance as 0 for root. For left subtree, we pass the Horizontal Distance as Horizontal distance of root minus 1. For right subtree, we pass the Horizontal Distance as Horizontal Distance of root plus 1.
We can do inorder traversal of the given Binary Tree. While traversing the tree, we can recursively calculate HDs. We initially pass the horizontal distance as 0 for root. For left subtree, we pass the Horizontal Distance as Horizontal distance of root minus 1. For right subtree, we pass the Horizontal Distance as Horizontal Distance of root plus 1.
// A wrapper over VerticalSumUtil() private void VerticalSum(TreeNode root) { // base case if (root == null) { return; } // Creates an empty hashMap hM HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); // Calls the VerticalSumUtil() to store the vertical sum values in hM VerticalSumUtil(root, 0, hM); // Prints the values stored by VerticalSumUtil() if (hM != null) { System.out.println(hM.entrySet()); } } // Traverses the tree in Inoorder form and builds a hashMap hM that // contains the vertical sum private void VerticalSumUtil(TreeNode root, int hD, HashMap<Integer, Integer> hM) { // base case if (root == null) { return; } // Store the values in hM for left subtree VerticalSumUtil(root.left(), hD - 1, hM); // Update vertical sum for hD of this node int prevSum = (hM.get(hD) == null) ? 0 : hM.get(hD); hM.put(hD, prevSum + root.key()); // Store the values in hM for right subtree VerticalSumUtil(root.right(), hD + 1, hM); }