Wednesday, April 13, 2016

Vertical Sum in Binary Tree | Set (Space Optimized) - GeeksforGeeks

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.

`    ``// 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; }`
`    ``}`
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.
`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);`
`    ``}`