Calculate Tilt

[5, 1, 3]

2

[4, 2, 7, 1, 3, 6, 9]

21

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//     TreeNode(int val) { this.val = val; }
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;

Explanation

We can solve this problem using the framework established in the Overview section.

Return Values

If I'm at a node in the tree, what values do I need to calculate the tilt of the subtree rooted at that node?

1. The sum of the values in the left subtree.
2. The sum of the values in the right subtree.

This tells me that each recursive call should return the sum of the values in the subtree rooted at the current node. So in the body of the recursive function, I'll make recursive calls to the current node's left and right children, and then add the value of the current node to return the sum of the current subtree.

Before returning the sum of the current subtree, I'll also need to calculate the tilt of the current subtree. I can calculate the tilt of the current subtree as abs(left - right), and add that a global variable tilt that stores the total tilt of the tree. (see the Global Variables section for more details on why this is necessary).

// get the sum of current node's left and right subtrees
int left = dfs(node.left);
int right = dfs(node.right);
// calculate tilt of current subtree and add it to the global tilt variable
tilt += Math.abs(left - right);
// return the sum of the current subtree
return left + right + node.val;

Base Case

The tilt of an empty tree is 0.

Global Variables Note that the problem is asking for the total tilt of the tree, but each recursive call returns the sum of the nodes in the subtree rooted at a given node. Since these two values are different, we can use a global variable tilt to store the total tilt of the tree. This allows us to avoid using multiple return values in our recursive function, or having to pass the total tilt value from the parent to the child.

Helper Function

We don't need to pass values from the parent to the child to solve this problem. However, since we are using a global variable to store the total tilt of the tree, we should define tilt inside the body of our main function, and then introduce a helper function to perform the recursive calls. This way, no code outside of the main function will have access to the tilt variable.

Inside the main function, we can initiate the call to the helper function, passing in the root of the tree as an argument. We return the value of tilt after the recursive helper function has finished executing.

Solution

class Solution {
    private int tilt = 0;
    
    public int findTilt(TreeNode root) {
        dfs(root);
        return tilt;
    }
    
    private int dfs(TreeNode node) {
        // base case
        if (node == null) {
            return 0;
        }
        // get the sum of the current node's left and right subtrees
        int left = dfs(node.left);
        int right = dfs(node.right);
        // calculate tilt of current subtree, and add it to the global tilt variable
        tilt += Math.abs(left - right);
        // return the sum of the current subtree
        return left + right + node.val;
    }
}