563. Binary Tree Tilt

📝 Problem Details

• Title: 563. Binary Tree Tilt
• Link: https://leetcode.com/problems/binary-tree-tilt/
• Difficulty: Easy
• Tags/Categories: Trees DFS

💭What Were My Initial Thoughts?

- dfs 
- need to find the *sum of every tree node's tilt*
	- tilt = abs between the sum of all nodes in the left subtree and nodes in the right subtree
	- if a node does not have a left or right child, treat the sum as a 0

🤔What Did I Struggle With?

~ helper function was required for this problem, could solve wiht DFS in the singular function 

💡 Explanation of Solution

- init the total tilt value as a public class member 
- have a helper function SubtreeSum to conduct the DFS
	- if the current node is null return 0
	- recursively call the function of the left and right subtrees 
	- calculate the tilt up until this node --> abs(leftSum - rightSum)
	- add this to the total tilt 
	- return the sum of the left and right subtrees and the current node value 

⌛ Complexity Analysis

💻 Implementation of Solution

class Solution {
public:
    int totalTilt = 0;
 
    int subtreeSum(TreeNode* root) {
        if(root == nullptr) return 0;
 
        int leftSum = subtreeSum(root->left);
        int rightSum = subtreeSum(root->right);
 
        int tilt = abs(leftSum - rightSum);
        totalTilt += tilt;
 
        return leftSum + rightSum + root->val;
    }
 
    int findTilt(TreeNode* root) {
        subtreeSum(root);
        return totalTilt;
    }
};