Vertical Sum in Binary Tree | Set (Space Optimized) - GeeksforGeeks
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.
X. Using double link list
http://www.geeksforgeeks.org/vertical-sum-in-a-given-binary-tree/
http://www.geeksforgeeks.org/vertical-sum-in-a-given-binary-tree/
Read full article from Vertical Sum in Binary Tree | Set (Space Optimized) - GeeksforGeeks
Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.
X. Using double link list
// Prints vertical sum of different vertical // lines in tree. This method mainly uses // verticalSumDLLUtil(). static void verticalSumDLL(TNode root) { // Create a doubly linked list node to // store sum of lines going through root. // Vertical sum is initialized as 0. LLNode llnode = new LLNode(0); // Compute vertical sum of different lines verticalSumDLLUtil(root, llnode); // llnode refers to sum of vertical line // going through root. Move llnode to the // leftmost line. while (llnode.prev != null) llnode = llnode.prev; // Prints vertical sum of all lines starting // from leftmost vertical line while (llnode != null) { System.out.print(llnode.data +" "); llnode = llnode.next; } } // Constructs linked list static void verticalSumDLLUtil(TNode tnode, LLNode llnode) { // Add current node's data to its vertical line llnode.data = llnode.data + tnode.data; // Recursively process left subtree if (tnode.left != null) { if (llnode.prev == null) { llnode.prev = new LLNode(0); llnode.prev.next = llnode; } verticalSumDLLUtil(tnode.left, llnode.prev); } // Process right subtree if (tnode.right != null) { if (llnode.next == null) { llnode.next = new LLNode(0); llnode.next.prev = llnode; } verticalSumDLLUtil(tnode.right, llnode.next); } } // Doubly Linked List Node static class LLNode { int data; LLNode prev, next; public LLNode(int d) { data = d; } }
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.
class Tree { private TreeNode root; // Constructors public Tree() { root = null; } public Tree(TreeNode n) { root = n; } // Method to be called by the consumer classes like Main class public void VerticalSumMain() { VerticalSum(root); } // 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); }http://www.geeksforgeeks.org/vertical-sum-in-a-given-binary-tree/
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); }