Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findTilt(self, root: TreeNode) -> int:
        self.total_tilt = 0

        def postorder(node):
            if not node:
                return 0
            left_sum = postorder(node.left)
            right_sum = postorder(node.right)
            self.total_tilt += abs(left_sum - right_sum)
            return node.val + left_sum + right_sum

        postorder(root)
        return self.total_tilt
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int totalTilt = 0;
    int postorder(TreeNode* node) {
        if (!node) return 0;
        int left = postorder(node->left);
        int right = postorder(node->right);
        totalTilt += abs(left - right);
        return node->val + left + right;
    }
    int findTilt(TreeNode* root) {
        postorder(root);
        return totalTilt;
    }
};
      

// Definition for a binary tree node.
public 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;
    }
}

class Solution {
    private int totalTilt = 0;
    public int findTilt(TreeNode root) {
        postorder(root);
        return totalTilt;
    }
    private int postorder(TreeNode node) {
        if (node == null) return 0;
        int left = postorder(node.left);
        int right = postorder(node.right);
        totalTilt += Math.abs(left - right);
        return node.val + left + right;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findTilt = function(root) {
    let totalTilt = 0;
    function postorder(node) {
        if (!node) return 0;
        let left = postorder(node.left);
        let right = postorder(node.right);
        totalTilt += Math.abs(left - right);
        return node.val + left + right;
    }
    postorder(root);
    return totalTilt;
};
      

Problem Description

Given the root of a binary tree, calculate the total tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. If a node does not have a left child, the sum for the left subtree is considered 0; similarly for the right child.

The tilt of the whole tree is the sum of all nodes' tilts.

Constraints:

• Each node's value is an integer.
• The number of nodes in the tree is in the range [0, 10⁴].
• The tree may be empty.

Thought Process

To solve this problem, we need to compute, for every node, the sum of all values in its left subtree and right subtree, calculate their absolute difference (the tilt), and then add up all these tilts for the entire tree.

A brute-force approach might be to, for each node, traverse its left and right subtrees to sum their values, but this would result in a lot of repeated work, leading to poor performance.

To optimize, we can use a post-order traversal (left-right-root) so that when visiting a node, we already know the sum of its left and right subtrees. This way, we avoid redundant calculations, and can accumulate the tilt as we go up the tree.

Solution Approach

Let's break down the steps for an efficient solution:

1. Use Post-Order Traversal:
   • We traverse the tree in post-order (left child, right child, then node itself).
   • This ensures that when we are at a node, we've already computed the sum of values for its left and right subtrees.
2. Compute Subtree Sums:
   • For each node, recursively compute the sum of its left and right subtrees.
   • The tilt for the current node is abs(left_sum - right_sum).
3. Accumulate the Tilt:
   • Maintain a variable (e.g., total_tilt) to accumulate the tilt of each node as we traverse the tree.
4. Return the Total Tilt:
   • After the traversal, total_tilt will hold the answer.

This approach ensures that each node is visited only once, and all calculations are done efficiently.

Example Walkthrough

Consider the following binary tree:

        4
       / \
      2   9
     / \   \
    3   5   7
  

• Start at the leaves:
  • Node 3 and Node 5: both have no children, so their tilts are 0.
  • Node 7: no children, tilt is 0.
• Move up to Node 2:
  • Left sum = 3 (from Node 3), right sum = 5 (from Node 5)
  • Tilt = |3 - 5| = 2
• Node 9:
  • Left sum = 0, right sum = 7 (from Node 7)
  • Tilt = |0 - 7| = 7
• Root Node 4:
  • Left sum = 2 + 3 + 5 = 10 (Node 2 + its children)
  • Right sum = 9 + 7 = 16 (Node 9 + its child)
  • Tilt = |10 - 16| = 6
• Total Tilt: 2 (Node 2) + 7 (Node 9) + 6 (Node 4) + 0 (Node 3) + 0 (Node 5) + 0 (Node 7) = 15

Time and Space Complexity

• Brute-force Approach:
  • For every node, traverse its left and right subtrees to compute their sums.
  • This leads to O(N^2) time complexity, where N is the number of nodes, due to repeated subtree traversals.
• Optimized Approach (Post-order Traversal):
  • Each node is visited exactly once.
  • At each node, we do O(1) work (sum and tilt calculation).
  • Time Complexity: O(N)
  • Space Complexity: O(H), where H is the height of the tree (due to recursion stack). In the worst case (skewed tree), H = N; in a balanced tree, H = log N.

Summary

The Binary Tree Tilt problem is efficiently solved using a post-order traversal, where we calculate the sum and tilt of each subtree in a single pass. By accumulating the tilt as we traverse, we avoid redundant computations and achieve optimal O(N) time complexity. This approach is both elegant and practical, making use of the natural recursive structure of binary trees.