Problem Description

You are given the root of a binary tree. Your task is to calculate the sum of tilts for all nodes in the tree.

The tilt of a node is defined as the absolute difference between:

• The sum of all node values in its left subtree
• The sum of all node values in its right subtree

For nodes without a left child, the sum of the left subtree is considered 0. The same rule applies for nodes without a right child.

The goal is to return the total sum of tilts for every node in the tree.

Example breakdown:

• For each node, calculate the sum of all values in its left subtree
• Calculate the sum of all values in its right subtree
• The tilt of that node = |left_sum - right_sum|
• Add up all the tilts from every node in the tree

The solution uses a depth-first search (DFS) approach where:

1. The function recursively calculates the sum of node values for each subtree
2. While calculating these sums, it also computes the tilt at each node
3. The tilt values are accumulated in a running total
4. The function returns both the sum needed by parent nodes and maintains the tilt sum

The key insight is that we can calculate both the sum of subtree values (needed for parent calculations) and the tilt contribution in a single traversal of the tree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• We arrive at DFS: For tree problems, DFS is the natural choice for traversing and processing nodes.

Conclusion: The flowchart suggests using a Depth-First Search (DFS) approach for solving the Binary Tree Tilt problem.

This makes sense because:

1. We need to visit every node in the tree to calculate its tilt
2. To calculate a node's tilt, we first need information from its children (the sum of values in left and right subtrees)
3. DFS allows us to process children before their parents, enabling bottom-up computation
4. The recursive nature of DFS perfectly matches the recursive structure of the tree

The DFS pattern helps us:

• Traverse to the leaf nodes first
• Calculate subtree sums while returning from recursive calls
• Compute each node's tilt using the subtree sums
• Accumulate the total tilt sum across all nodes in a single traversal

Intuition

When we look at this problem, we need to calculate the tilt for every single node, where each node's tilt depends on the sum of all values in its left and right subtrees. This immediately suggests we need information from children before we can process a parent node - a classic bottom-up pattern.

Think about it this way: to find the tilt of a node, we need two pieces of information:

1. The sum of all values in its left subtree
2. The sum of all values in its right subtree

But here's the key insight - when we're calculating these sums for a parent node, we're essentially calculating the same information that its parent will need later. This means we can solve two problems at once:

• Calculate the tilt for the current node
• Return the sum of the current subtree for the parent's calculation

This dual-purpose approach naturally leads us to a recursive DFS solution where each recursive call does two things:

1. Returns the sum of all nodes in the subtree (needed by the parent)
2. Accumulates the tilt value in a global variable (our final answer)

The beauty of this approach is that we only traverse the tree once. As we bubble up from the leaves to the root:

• Leaf nodes have tilt = 0 (no children)
• Each parent calculates its tilt using the sums returned by its children
• We keep a running total of all tilts encountered

The formula at each node becomes:

• tilt = |left_sum - right_sum|
• return left_sum + right_sum + current_node_value

This way, each node provides exactly what its parent needs while contributing to our final answer - an elegant solution that leverages the recursive nature of trees.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a recursive DFS function that calculates both the subtree sum and the tilt contribution in a single traversal.

Let's break down the solution step by step:

1. Setting up the DFS function: We define an inner function dfs(root) that will:

• Return the sum of all node values in the subtree rooted at root
• Calculate and accumulate the tilt for the current node

2. Base case:

if root is None:
    return 0

When we reach a null node, we return 0 as the sum, which handles leaf nodes' missing children naturally.

3. Recursive calls:

l, r = dfs(root.left), dfs(root.right)

We recursively calculate:

• l: sum of all values in the left subtree
• r: sum of all values in the right subtree

4. Calculate and accumulate tilt:

nonlocal ans
ans += abs(l - r)

The tilt of the current node is |l - r|. We use nonlocal to access the ans variable from the outer scope and add the current node's tilt to our running total.

5. Return subtree sum:

return l + r + root.val

We return the total sum of the current subtree, which includes:

• Sum of left subtree (l)
• Sum of right subtree (r)
• Current node's value (root.val)

6. Main function execution:

ans = 0
dfs(root)
return ans

We initialize our answer to 0, call the DFS function starting from the root, and return the accumulated tilt sum.

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this could be O(n).

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Consider this binary tree:

       1
      / \
     2   3
    / \
   4   5

We'll trace through the DFS traversal and show how tilts are calculated bottom-up.

Step 1: Start DFS from root (node 1)

• Calls dfs(node 2) for left subtree
• Will later call dfs(node 3) for right subtree

Step 2: Process node 2's left subtree

• Calls dfs(node 4)
• Node 4 is a leaf, so:
  • l = dfs(None) = 0
  • r = dfs(None) = 0
  • Tilt of node 4 = |0 - 0| = 0
  • ans = 0 (first tilt added)
  • Returns 0 + 0 + 4 = 4

Step 3: Process node 2's right subtree

• Calls dfs(node 5)
• Node 5 is a leaf, so:
  • l = dfs(None) = 0
  • r = dfs(None) = 0
  • Tilt of node 5 = |0 - 0| = 0
  • ans = 0 (still 0)
  • Returns 0 + 0 + 5 = 5

Step 4: Complete processing node 2

• l = 4 (sum from left subtree)
• r = 5 (sum from right subtree)
• Tilt of node 2 = |4 - 5| = 1
• ans = 1 (accumulating tilts)
• Returns 4 + 5 + 2 = 11

Step 5: Process node 3

• Node 3 is a leaf, so:
  • l = dfs(None) = 0
  • r = dfs(None) = 0
  • Tilt of node 3 = |0 - 0| = 0
  • ans = 1 (unchanged)
  • Returns 0 + 0 + 3 = 3

Step 6: Complete processing root (node 1)

• l = 11 (sum of entire left subtree: 2+4+5)
• r = 3 (sum of entire right subtree: just 3)
• Tilt of node 1 = |11 - 3| = 8
• ans = 1 + 8 = 9
• Returns 11 + 3 + 1 = 15 (not used)

Final Result: The sum of all tilts = 9

Breaking down the tilts:

• Node 4: tilt = 0
• Node 5: tilt = 0
• Node 2: tilt = 1 (|4-5|)
• Node 3: tilt = 0
• Node 1: tilt = 8 (|11-3|)
• Total: 0 + 0 + 1 + 0 + 8 = 9

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node is visited exactly once during the traversal. At each node, the algorithm performs constant time operations:

• Calculating the absolute difference between left and right subtree sums: abs(l - r) - O(1)
• Adding to the running total: ans += abs(l - r) - O(1)
• Returning the sum: l + r + root.val - O(1)

Since we visit all n nodes exactly once and perform O(1) operations at each node, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the recursive call stack used during DFS traversal. In the worst case, the tree is completely unbalanced (e.g., a skewed tree where each node has only one child), resulting in a recursion depth equal to the number of nodes n. This would require O(n) space on the call stack.

In the best case (a perfectly balanced tree), the recursion depth would be O(log n), but we consider the worst-case scenario for space complexity analysis, which gives us O(n).

The only additional space used is the ans variable, which is O(1), so the overall space complexity remains O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Node Tilt with Subtree Sum

A frequent mistake is calculating the tilt using the node values themselves rather than the sum of all nodes in each subtree.

Incorrect approach:

# WRONG: Using only direct children values
tilt = abs(node.left.val - node.right.val)

Correct approach:

# RIGHT: Using sum of entire subtrees
left_sum = calculate_sum_and_tilt(node.left)  # Sum of ALL nodes in left subtree
right_sum = calculate_sum_and_tilt(node.right)  # Sum of ALL nodes in right subtree
tilt = abs(left_sum - right_sum)

2. Forgetting to Include Current Node Value in Return

Another common error is returning only the sum of left and right subtrees without including the current node's value, which breaks the calculation for parent nodes.

Incorrect approach:

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

Correct approach:

def dfs(node):
    if not node:
        return 0
    left_sum = dfs(node.left)
    right_sum = dfs(node.right)
    self.total_tilt += abs(left_sum - right_sum)
    return left_sum + right_sum + node.val  # RIGHT: Include current node value

3. Using Local Variable Instead of Instance/Nonlocal Variable

Attempting to use a regular local variable for accumulating tilts will fail because each recursive call creates its own scope.

Incorrect approach:

def findTilt(self, root):
    total_tilt = 0  # Local variable
  
    def dfs(node):
        if not node:
            return 0
        left_sum = dfs(node.left)
        right_sum = dfs(node.right)
        total_tilt += abs(left_sum - right_sum)  # ERROR: UnboundLocalError
        return left_sum + right_sum + node.val
  
    dfs(root)
    return total_tilt

Correct approaches:

# Option 1: Using instance variable
def findTilt(self, root):
    self.total_tilt = 0
  
    def dfs(node):
        # ... rest of code
        self.total_tilt += abs(left_sum - right_sum)
        # ...
  
    dfs(root)
    return self.total_tilt

# Option 2: Using nonlocal keyword
def findTilt(self, root):
    total_tilt = 0
  
    def dfs(node):
        nonlocal total_tilt
        # ... rest of code
        total_tilt += abs(left_sum - right_sum)
        # ...
  
    dfs(root)
    return total_tilt

4. Calculating Tilt Only for Leaf Nodes

Some might mistakenly think tilt is only calculated for leaf nodes or only for non-leaf nodes.

Incorrect assumption:

def dfs(node):
    if not node:
        return 0
  
    left_sum = dfs(node.left)
    right_sum = dfs(node.right)
  
    # WRONG: Only adding tilt for leaf nodes
    if not node.left and not node.right:
        self.total_tilt += abs(left_sum - right_sum)
  
    return left_sum + right_sum + node.val

Correct approach: Every node (including leaves, internal nodes, and root) contributes to the total tilt. For leaf nodes, the tilt is always 0 (since both subtrees are empty), but we still include them in our calculation.