Approach 1: Using Recursion
From the problem statement, it is clear that we need to find the tilt value at every node of the given tree and add up all the tilt values to obtain the final result. To find the tilt value at any node, we need to subtract the sum of all the nodes in its left subtree and the sum of all the nodes in its right subtree.
Thus, to find the solution, we make use of a recursive function
traverse which when called from any node, returns the sum of the nodes below the current node including itself. With the help of such sum values for the right and left subchild of any node, we can directly obtain the tilt value corresponding to that node.
The below animation depicts how the value passing and tilt calculation:
- Time complexity : . where is the number of nodes. Each node is visited once.
- Space complexity : . In worst case when the tree is skewed depth of tree will be . In average case depth will be .
Analysis written by: @vinod23