LeetCode 563 - Binary Tree Tilt

LeetCode Problem 563

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to compute the total tilt of an entire binary tree. Every node in the tree has its own tilt, and the final answer is the sum of all individual node tilts.

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

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

If a subtree does not exist, its sum is considered 0.

For example, suppose a node has:

• Left subtree sum = 8
• Right subtree sum = 3

Then the node's tilt is:

$|8-3|=5$

The input is the root of a binary tree. Each node contains:

• An integer value
• A left child pointer
• A right child pointer

The output is a single integer representing the sum of tilts across all nodes in the tree.

The constraints tell us that the tree can contain up to 10^4 nodes. This is large enough that inefficient repeated traversals can become expensive. Since node values may be negative, subtree sums can also become negative, so the algorithm must correctly handle signed arithmetic.

Several edge cases are important:

• An empty tree should return 0
• A single-node tree has tilt 0, because both subtree sums are 0
• Trees with only left or only right children create highly unbalanced structures
• Negative values can produce unexpected subtree sums if absolute difference is not handled carefully

The problem guarantees that the input is a valid binary tree, so we do not need to validate structure correctness.

Approaches

Brute Force Approach

A straightforward solution is to compute the tilt of every node independently.

For each node:

1. Compute the sum of the left subtree
2. Compute the sum of the right subtree
3. Take the absolute difference
4. Add the result to a global total

The problem is that subtree sums are recomputed many times.

Consider a skewed tree:

1
 \
  2
   \
    3
     \
      4

When computing the tilt of node 1, we traverse almost the entire tree. Then when computing the tilt of node 2, we again traverse most of the remaining tree, and so on.

This repeated work causes the time complexity to degrade to O(n^2) in the worst case.

Although this approach is correct, it is inefficient for large trees.

Optimal Approach

The key observation is that while computing the tilt of a node, we already need the sums of its left and right subtrees.

Instead of recomputing subtree sums repeatedly, we can compute them once using postorder traversal.

Postorder traversal processes nodes in this order:

1. Left subtree
2. Right subtree
3. Current node

This order is perfect because by the time we process a node, we already know:

• The total sum of the left subtree
• The total sum of the right subtree

So we can:

1. Compute the node's tilt immediately
2. Add it to a running total
3. Return the subtree sum upward to the parent

This eliminates redundant work and gives a linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Recomputes subtree sums repeatedly
Optimal	O(n)	O(h)	Single postorder traversal computes both sums and tilts

Here, h is the height of the tree.

Algorithm Walkthrough

1. Initialize a variable called total_tilt to store the accumulated tilt of all nodes.
2. Define a recursive helper function that returns the sum of the subtree rooted at the current node.
3. In the helper function, first check whether the current node is None. If it is, return 0 because an empty subtree contributes no value.
4. Recursively compute the sum of the left subtree. This ensures the entire left side has already been processed before handling the current node.
5. Recursively compute the sum of the right subtree for the same reason.
6. Compute the current node's tilt using the absolute difference between the left and right subtree sums.

For a node with left sum L and right sum R:

$|L-R|$

1. Add this tilt value to total_tilt.
2. Return the total subtree sum rooted at the current node. This includes:

• Current node value
• Left subtree sum
• Right subtree sum

For a node value v:

$v+L+R$

1. Start the recursion from the root node.
2. After traversal finishes, return total_tilt.

Why it works

The algorithm works because every node is processed only after both of its subtrees have already been fully evaluated. This guarantees that when computing a node's tilt, the left and right subtree sums are correct and complete.

The recursive helper returns the exact subtree sum for every node, which allows parent nodes to compute their own tilt correctly. Since every node contributes exactly once to total_tilt, the final answer is the sum of all node tilts.

Python Solution

# 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

from typing import Optional

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

        def subtree_sum(node: Optional[TreeNode]) -> int:
            nonlocal total_tilt

            if not node:
                return 0

            left_sum = subtree_sum(node.left)
            right_sum = subtree_sum(node.right)

            total_tilt += abs(left_sum - right_sum)

            return node.val + left_sum + right_sum

        subtree_sum(root)

        return total_tilt

The implementation uses a nested helper function called subtree_sum. This function performs the postorder traversal and returns the total sum of the current subtree.

The base case handles None nodes by returning 0.

For every non-null node:

1. The left subtree sum is computed recursively.
2. The right subtree sum is computed recursively.
3. The node's tilt is calculated using the absolute difference.
4. The tilt is added to the running total.
5. The complete subtree sum is returned upward.

The nonlocal keyword allows the helper function to modify total_tilt defined in the outer scope.

This implementation visits every node exactly once, making it efficient even for large trees.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTilt(root *TreeNode) int {
    totalTilt := 0

    var subtreeSum func(node *TreeNode) int

    subtreeSum = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftSum := subtreeSum(node.Left)
        rightSum := subtreeSum(node.Right)

        if leftSum > rightSum {
            totalTilt += leftSum - rightSum
        } else {
            totalTilt += rightSum - leftSum
        }

        return node.Val + leftSum + rightSum
    }

    subtreeSum(root)

    return totalTilt
}

The Go implementation follows the same postorder traversal strategy as the Python version.

One notable difference is that Go does not have a built-in abs function for integers in the standard library. Instead, the code manually computes the absolute difference using a conditional statement.

The recursive helper is defined as a function variable so it can recursively reference itself.

Nil pointers in Go serve the same role as None in Python.

Worked Examples

Example 1

Input:

    1
   / \
  2   3

We process the tree using postorder traversal.

Node	Left Sum	Right Sum	Tilt	Running Total	Returned Sum
2	0	0	0	0	2
3	0	0	0	0	3
1	2	3	1	1	6

Final answer:

1

Example 2

Input:

        4
       / \
      2   9
     / \   \
    3   5   7

Traversal order is:

3 → 5 → 2 → 7 → 9 → 4

Node	Left Sum	Right Sum	Tilt	Running Total	Returned Sum
3	0	0	0	0	3
5	0	0	0	0	5
2	3	5	2	2	10
7	0	0	0	2	7
9	0	7	7	9	16
4	10	16	6	15	30

Final answer:

15

Example 3

Input:

         21
        /  \
       7    14
      / \   / \
     1   1 2   2
    / \
   3   3

Postorder traversal computes subtree sums from the leaves upward.

Node	Left Sum	Right Sum	Tilt	Running Total
3	0	0	0	0
3	0	0	0	0
1	3	3	0	0
1	0	0	0	0
7	7	1	6	6
2	0	0	0	6
2	0	0	0	6
14	2	2	0	6
21	15	18	3	9

Final answer:

9

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack stores at most tree height frames

The algorithm performs a single DFS traversal of the tree. Each node contributes constant work:

• Compute left subtree sum
• Compute right subtree sum
• Compute tilt
• Return subtree sum

Therefore the total running time is linear in the number of nodes.

The auxiliary space complexity comes from recursion depth. In a balanced tree, the height is O(log n). In the worst case of a completely skewed tree, the height becomes O(n).

Test Cases

# Definition for testing
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):
        total_tilt = 0

        def subtree_sum(node):
            nonlocal total_tilt

            if not node:
                return 0

            left_sum = subtree_sum(node.left)
            right_sum = subtree_sum(node.right)

            total_tilt += abs(left_sum - right_sum)

            return node.val + left_sum + right_sum

        subtree_sum(root)

        return total_tilt

sol = Solution()

# Example 1
root1 = TreeNode(1, TreeNode(2), TreeNode(3))
assert sol.findTilt(root1) == 1  # basic balanced tree

# Example 2
root2 = TreeNode(
    4,
    TreeNode(2, TreeNode(3), TreeNode(5)),
    TreeNode(9, None, TreeNode(7))
)
assert sol.findTilt(root2) == 15  # multiple subtree tilts

# Example 3
root3 = TreeNode(
    21,
    TreeNode(
        7,
        TreeNode(1, TreeNode(3), TreeNode(3)),
        TreeNode(1)
    ),
    TreeNode(14, TreeNode(2), TreeNode(2))
)
assert sol.findTilt(root3) == 9  # deeper tree

# Empty tree
assert sol.findTilt(None) == 0  # no nodes

# Single node
root4 = TreeNode(5)
assert sol.findTilt(root4) == 0  # no children

# Left skewed tree
root5 = TreeNode(4, TreeNode(3, TreeNode(2, TreeNode(1))))
assert sol.findTilt(root5) == 10  # highly unbalanced

# Right skewed tree
root6 = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
assert sol.findTilt(root6) == 8  # one-sided tree

# Negative values
root7 = TreeNode(-10, TreeNode(-20), TreeNode(-30))
assert sol.findTilt(root7) == 10  # negative subtree sums

# Mixed positive and negative
root8 = TreeNode(5, TreeNode(-3), TreeNode(2))
assert sol.findTilt(root8) == 5  # mixed signs

Test	Why
[1,2,3]	Validates basic tilt computation
[4,2,9,3,5,null,7]	Tests multiple subtree calculations
[21,7,14,1,1,2,2,3,3]	Tests deeper recursion
[]	Validates empty tree handling
[5]	Validates single-node tree
Left-skewed tree	Tests worst-case recursion depth
Right-skewed tree	Tests asymmetric structure
Negative values	Ensures signed arithmetic works correctly
Mixed positive/negative	Verifies absolute difference handling

Edge Cases

Empty Tree

An empty tree contains no nodes, so there are no tilts to compute. A buggy implementation might attempt to access properties of None and crash.

The implementation handles this safely because the recursive helper immediately returns 0 when given a null node. As a result, findTilt(None) correctly returns 0.

Single Node Tree

A tree with only one node has no left or right subtree. Both subtree sums are therefore 0, so the tilt is:

$|0-0|=0$

Some implementations accidentally treat leaf nodes differently or forget to include them in traversal logic. This solution naturally handles leaf nodes through the recursive base case.

Highly Unbalanced Trees

A skewed tree behaves similarly to a linked list and can expose inefficiencies in brute-force approaches because subtree sums are repeatedly recomputed.

The optimal solution still processes each node exactly once. Even though recursion depth becomes O(n) in the worst case, the total computation remains linear.

Negative Node Values

Since node values may be negative, subtree sums can also become negative. Incorrect implementations sometimes forget to apply absolute value correctly.

For example:

$|-20-(-30)|=10$

The implementation always uses absolute difference, ensuring the tilt remains non-negative regardless of subtree signs.