title: Binary Tree Tilt
slug: binary-tree-tilt
difficulty: easy
leetcode_id: 563
leetcode_url: https://leetcode.com/problems/binary-tree-tilt/
categories:
  - trees
  - recursion
patterns:
  - slug: dfs
    is_optimal: true
  - slug: tree-traversal
    is_optimal: false

function_signature: "def find_tilt(root: TreeNode) -> int:"

test_cases:
  visible:
    - input: { root: [1, 2, 3] }
      expected: 1
    - input: { root: [4, 2, 9, 3, 5, null, 7] }
      expected: 15
    - input: { root: [21, 7, 14, 1, 1, 2, 2, 3, 3] }
      expected: 9
  hidden:
    - input: { root: [] }
      expected: 0
    - input: { root: [1] }
      expected: 0
    - input: { root: [1, 2, null] }
      expected: 2
    - input: { root: [1, null, 3] }
      expected: 3
    - input: { root: [0, 0, 0] }
      expected: 0
    - input: { root: [5, 5, 5, 5, 5, 5, 5] }
      expected: 0
    - input: { root: [1, 2, 3, 4, null, 5, 6] }
      expected: 11

description: |
  Given the `root` of a binary tree, return *the sum of every tree node's **tilt***.

  The **tilt** of a tree node is the **absolute difference** between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as `0`. The rule is similar if the node does not have a right child.

constraints: |
  - The number of nodes in the tree is in the range `[0, 10^4]`
  - `-1000 <= Node.val <= 1000`

examples:
  - input: "root = [1,2,3]"
    output: "1"
    explanation: "Tilt of node 2: |0-0| = 0 (no children). Tilt of node 3: |0-0| = 0 (no children). Tilt of node 1: |2-3| = 1 (left subtree sum is 2, right subtree sum is 3). Total tilt: 0 + 0 + 1 = 1."
  - input: "root = [4,2,9,3,5,null,7]"
    output: "15"
    explanation: "Tilt of leaves (3, 5, 7): 0 each. Tilt of node 2: |3-5| = 2. Tilt of node 9: |0-7| = 7. Tilt of node 4: |10-16| = 6. Total: 0 + 0 + 0 + 2 + 7 + 6 = 15."
  - input: "root = [21,7,14,1,1,2,2,3,3]"
    output: "9"
    explanation: "Sum the absolute differences between left and right subtree sums for each node."

explanation:
  intuition: |
    Imagine each node in the tree as a balance scale. On the left pan sits the total weight (sum) of all nodes in the left subtree, and on the right pan sits the total weight of the right subtree. The *tilt* is how much the scale tips — the absolute difference between these two weights.

    Think of it like this: we need to visit every node and measure how "unbalanced" it is. But here's the insight — to calculate a node's tilt, we need to know the sum of its entire left subtree and its entire right subtree. This naturally suggests a **bottom-up approach**: calculate the sums from the leaves up, because a parent's subtree sum depends on its children's subtree sums.

    The recursive pattern emerges: for each node, we recursively get the total sum of the left subtree and the right subtree. The tilt at this node is `|left_sum - right_sum|`. We accumulate all tilts as we traverse, and the node returns its own value plus both subtree sums (so its parent can use it).

    This is a classic example of **postorder traversal** — we process children before the parent because we need the children's results to compute the parent's answer.

  approach: |
    We solve this using **DFS with Postorder Traversal**:

    **Step 1: Set up a variable to accumulate total tilt**

    - Use a variable (or class attribute) `total_tilt` initialised to `0`
    - This accumulates the tilt of every node as we traverse

    &nbsp;

    **Step 2: Define a recursive helper function**

    - The helper takes a node and returns the **sum of all values in that subtree**
    - Base case: if node is `None`, return `0` (empty subtree has sum 0)

    &nbsp;

    **Step 3: Recursively compute subtree sums**

    - Recursively call the helper on `node.left` to get `left_sum`
    - Recursively call the helper on `node.right` to get `right_sum`
    - This is postorder: we process children before doing work at the current node

    &nbsp;

    **Step 4: Calculate tilt and accumulate**

    - Compute this node's tilt: `|left_sum - right_sum|`
    - Add it to `total_tilt`

    &nbsp;

    **Step 5: Return the subtree sum**

    - Return `node.val + left_sum + right_sum`
    - This gives the parent node everything it needs to calculate its own tilt

    &nbsp;

    After the traversal completes, `total_tilt` contains the answer.

  common_pitfalls:
    - title: Confusing Tilt with Subtree Sum
      description: |
        The tilt at a node is NOT the sum of its subtree — it's the **absolute difference** between left and right subtree sums.

        A common mistake is returning the tilt instead of the subtree sum from the recursive function. Remember: the function returns subtree sum (so parents can use it), but we **accumulate** tilt separately.
      wrong_approach: "Returning tilt from recursive function"
      correct_approach: "Return subtree sum; accumulate tilt in a separate variable"

    - title: Forgetting to Include the Node's Own Value
      description: |
        When returning the subtree sum, you must include the current node's value: `node.val + left_sum + right_sum`.

        If you only return `left_sum + right_sum`, the parent won't get the correct subtree sum, and its tilt calculation will be wrong.
      wrong_approach: "return left_sum + right_sum"
      correct_approach: "return node.val + left_sum + right_sum"

    - title: Using Preorder Instead of Postorder
      description: |
        You cannot calculate a node's tilt before knowing its subtree sums. If you try to process the node before its children (preorder), you won't have the information you need.

        The solution requires **postorder**: left subtree → right subtree → current node.
      wrong_approach: "Process node before recursing into children"
      correct_approach: "Recurse into children first, then calculate tilt"

  key_takeaways:
    - "**Postorder for aggregation**: When a node's answer depends on its children's results, use postorder traversal (process children before parent)"
    - "**Dual-purpose recursion**: The recursive function returns subtree sum (for parent's use) while accumulating tilt (for the final answer)"
    - "**Bottom-up thinking**: Many tree problems become clearer when you think from leaves up to root"
    - "**Pattern recognition**: This same technique applies to problems like finding unbalanced nodes, calculating tree diameter, or validating BST properties"

  time_complexity: "O(n). We visit each node exactly once, performing O(1) work at each node."
  space_complexity: "O(h) where h is the tree height. The recursion stack depth equals the tree height — O(log n) for balanced trees, O(n) for skewed trees."

solutions:
  - approach_name: DFS Postorder Traversal
    is_optimal: true
    code: |
      class TreeNode:
          def __init__(self, val=0, left=None, right=None):
              self.val = val
              self.left = left
              self.right = right

      def find_tilt(root: TreeNode | None) -> int:
          total_tilt = 0

          def subtree_sum(node: TreeNode | None) -> int:
              nonlocal total_tilt

              # Base case: empty subtree has sum 0
              if not node:
                  return 0

              # Postorder: get children's sums first
              left_sum = subtree_sum(node.left)
              right_sum = subtree_sum(node.right)

              # Calculate and accumulate this node's tilt
              total_tilt += abs(left_sum - right_sum)

              # Return total sum of this subtree for parent's use
              return node.val + left_sum + right_sum

          subtree_sum(root)
          return total_tilt
    explanation: |
      **Time Complexity:** O(n) — Visit each node once.

      **Space Complexity:** O(h) — Recursion stack depth equals tree height.

      We use postorder DFS where each call returns the subtree sum while accumulating tilt. The `nonlocal` keyword lets the inner function modify `total_tilt`. After traversing all nodes, we have the sum of all tilts.

  - approach_name: DFS with Class Variable
    is_optimal: false
    code: |
      class Solution:
          def find_tilt(self, root: TreeNode | None) -> int:
              self.total_tilt = 0

              def dfs(node: TreeNode | None) -> int:
                  if not node:
                      return 0

                  # Get subtree sums from children
                  left_sum = dfs(node.left)
                  right_sum = dfs(node.right)

                  # Add this node's tilt to running total
                  self.total_tilt += abs(left_sum - right_sum)

                  # Return subtree sum including this node
                  return node.val + left_sum + right_sum

              dfs(root)
              return self.total_tilt
    explanation: |
      **Time Complexity:** O(n) — Same as the functional approach.

      **Space Complexity:** O(h) — Recursion stack depth.

      This class-based version uses `self.total_tilt` instead of `nonlocal`. Some find this more readable, and it's the typical LeetCode solution format. The logic is identical to the functional approach.
