Today I wanted to do a quick recursive problem that came to my attention. It took me about 20 mins to finalize this the way I wanted it… (5-10 too many). So basically here we are asked to morph a given binary tree so that every node in the tree will be equal to all the nodes on its left plus itself. Smells like tree traversal! And whenever we have tree traversals we can mostly use recursion to cover our cases. Below is the code!
How to Morph a Binary Tree From Its Left Subsum
|
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 |
/* * @Author: Ajk Palikuqi * * @Question: How to Morph a Binary Tree From Its Left Subsum. * */ package iqLib.treeLib; import iqLib.treeLib.TreeNode; public class TreeMorphLeftSum { /* * Returns the tree under root morphed in a way so that every node is equal * to the sum of the nodes on its left nodes and itself. */ public static TreeNode MorphTree(TreeNode root) { if (root != null) { morphTreeHelper(root, 0); } return root; } /* * Recursive method to return the tree with nodes morphed to the sum of all * their left children plus previousLeftSum in their value. */ private static int morphTreeHelper(TreeNode root, int previousLeftSum) { if (root == null) { return 0; } int currentLeftValue = morphTreeHelper(root.getLeft(), previousLeftSum) + root.getValue(); root.setValue(currentLeftValue); morphTreeHelper(root.getRight(), currentLeftValue); return currentLeftValue; } } |
Basically, we keep track of the previousLeftSum. Then we do an inorder traversal.
Go left first, updated leftmost nodes, then update the node we’re looking at. At the end update the rightmost node.
Great! You probably know how to transform trees now and how to do tree traversals.
Hope you guys enjoyed it… And I’ll see you guys next time 😉
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017