LeetCode 563: Binary Tree Tilt Solution in Python – A Step-by-Step Guide

What Is LeetCode 563: Binary Tree Tilt?

In LeetCode 563: Binary Tree Tilt, you’re given the root of a binary tree, and your task is to return the total tilt, defined as the sum of each node’s tilt, where a node’s tilt is the absolute difference between the sum of all values in its left subtree and its right subtree (null subtrees sum to 0). For example, with root = [1,2,3], the total tilt is 1 (tilt at 1 = |2 - 3| = 1, tilt at 2 and 3 = 0). This problem builds on LeetCode 104: Maximum Depth of Binary Tree for tree traversal but shifts focus to computing differences between subtrees.

Problem Statement

• Input: root (TreeNode)—root of a binary tree.
• Output: Integer—total tilt of the tree.
• Rules: Tilt of a node = |sum(left subtree) - sum(right subtree)|; total tilt = sum of all nodes’ tilts; null sums to 0.

Constraints

• Number of nodes: 0 to 10⁴.
• Node values: -100 to 100.

Examples

• Input: root = [1,2,3]
• Output: 1
• Tree:
``` 1 / \ 2 3 ```
• Tilt at 1 = |2 - 3| = 1, at 2 = 0, at 3 = 0; Total = 1.
• Input: root = [4,2,9,3,5,null,7]
• Output: 15
• Tree:
``` 4 / \ 2 9 / \ \ 3 5 7 ```
• Tilt at 4 = |8 - 16| = 8, at 2 = |3 - 5| = 2, at 9 = |0 - 7| = 7; Total = 8 + 2 + 7 = 15.
• Input: root = []
• Output: 0
• Empty tree.

Understanding the Problem: Calculating Tree Tilt

To solve LeetCode 563: Binary Tree Tilt in Python, we need to compute the total tilt of a binary tree by summing the tilt at each node, where tilt is the absolute difference between the sums of its left and right subtrees. With up to 10⁴ nodes, a naive approach might compute subtree sums repeatedly (O(n²)), but we can optimize by traversing the tree once, calculating sums and tilts together. The problem tests tree traversal and state management. We’ll explore:

• Best Solution (Recursive DFS with Tilt Tracking): O(n) time, O(h) space (n = nodes, h = height)—fast and simple.
• Alternative Solution (Iterative BFS with Post-Order Simulation): O(n) time, O(n) space—thorough but complex.

Let’s dive into the recursive solution with a friendly breakdown!

Best Solution: Recursive DFS with Tilt Tracking

Why Recursive DFS Wins

The recursive DFS with tilt tracking is the best for LeetCode 563 because it computes the total tilt in O(n) time and O(h) space by traversing the tree once, calculating subtree sums bottom-up and accumulating tilt values at each node using a global variable or return value. It’s like climbing the tree, weighing each branch as you go, and adding up the imbalances—all in a single, smooth journey!

How It Works

Think of this as a tree-tilt balancer:

• Step 1: Initialize Total Tilt:
• Use a class variable or global to track total tilt (e.g., self.tilt_sum).
• Step 2: Recursive DFS:
• For each node, compute sum of left and right subtrees recursively.
• Calculate node’s tilt = |left_sum - right_sum|.
• Add tilt to total.
• Step 3: Return Subtree Sum:
• Return sum of node’s value plus left and right sums.
• Step 4: Base Case:
• If node is None, return 0 (null subtree sum).
• Step 5: Return Total:
• Final total tilt after traversal.
• Why It Works:
• Bottom-up traversal computes sums once.
• Global tracking avoids redundant passes.

It’s like a tree-tilt tally master!

Step-by-Step Example

Example: root = [1,2,3]

• Init: self.tilt_sum = 0.
• Step 1: DFS(1):
• Left = DFS(2):
• No children, tilt = |0 - 0| = 0, return 2.
• Right = DFS(3):
• No children, tilt = |0 - 0| = 0, return 3.
• Tilt at 1 = |2 - 3| = 1, self.tilt_sum = 1.
• Return 1 + 2 + 3 = 6.
• Result: 1.

Example: root = [4,2,9,3,5,null,7]

• Step 1: DFS(4):
• Left = DFS(2):
• Left = DFS(3): No children, tilt = 0, return 3.
• Right = DFS(5): No children, tilt = 0, return 5.
• Tilt at 2 = |3 - 5| = 2, self.tilt_sum = 2, return 2 + 3 + 5 = 10.
• Right = DFS(9):
• Right = DFS(7): No children, tilt = 0, return 7.
• Tilt at 9 = |0 - 7| = 7, self.tilt_sum = 9, return 9 + 7 = 16.
• Tilt at 4 = |10 - 16| = 6, self.tilt_sum = 15, return 4 + 10 + 16 = 30.
• Result: 15.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass 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:
        # Step 1: Initialize total tilt as instance variable
        self.tilt_sum = 0

        # Step 2: Start DFS traversal
        def dfs(node):
            if not node:
                return 0

            # Step 3: Recursively get sums of left and right subtrees
            left_sum = dfs(node.left)
            right_sum = dfs(node.right)

            # Step 4: Calculate and add tilt for current node
            self.tilt_sum += abs(left_sum - right_sum)

            # Step 5: Return total sum of this subtree
            return left_sum + right_sum + node.val

        dfs(root)
        return self.tilt_sum

• Line 9: Global tilt tracker.
• Lines 12-14: Base case: null node returns 0.
• Lines 17-18: Recurse on left and right children.
• Line 21: Add node’s tilt to total.
• Line 24: Return subtree sum (node + children).
• Line 26: Trigger DFS, return total tilt.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h ≤ n).

It’s like a tree-tilt calculator!

Alternative Solution: Iterative BFS with Post-Order Simulation

Why an Alternative Approach?

The iterative BFS with post-order simulation uses a queue and stack to traverse the tree level-by-level, simulating post-order to compute sums and tilts, running in O(n) time and O(n) space. It’s thorough and avoids recursion, making it a good alternative for iteration fans or when stack space is a concern.

How It Works

Picture this as a tree-tilt leveler:

• Step 1: BFS to collect nodes in reverse order.
• Step 2: Process nodes bottom-up, compute sums and tilts.
• Step 3: Track total tilt.
• Step 4: Return total.

It’s like a tree-tilt level scanner!

Step-by-Step Example

Example: root = [1,2,3]

• Step 1: BFS Queue: [1], Stack: [1, 2, 3].
• Step 2: Process stack:
• 2: Sum = 2, Tilt = 0.
• 3: Sum = 3, Tilt = 0.
• 1: Left = 2, Right = 3, Tilt = |2 - 3| = 1, Total = 1.
• Result: 1.

Code for BFS Approach

Copy codefrom collections import deque

class Solution:
    def findTilt(self, root: TreeNode) -> int:
        if not root:
            return 0

        # Step 1: BFS to collect nodes
        queue = deque([root])
        stack = []
        while queue:
            node = queue.popleft()
            stack.append(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        # Step 2: Process bottom-up
        tilt_sum = 0
        sums = {}
        while stack:
            node = stack.pop()
            left_sum = sums.get(node.left, 0)
            right_sum = sums.get(node.right, 0)
            tilt_sum += abs(left_sum - right_sum)
            sums[node] = left_sum + right_sum + node.val

        return tilt_sum

• Lines 10-16: BFS builds stack in reverse order.
• Lines 19-25: Process stack, compute tilts and sums.
• Line 27: Return total tilt.
• Time Complexity: O(n)—single traversal.
• Space Complexity: O(n)—queue and stack.

It’s an iterative tilt tallier!

Comparing the Two Solutions

• Recursive DFS (Best):
• Pros: O(n), O(h), simple.
• Cons: Stack space.
• Iterative BFS (Alternative):
• Pros: O(n), O(n), no recursion.
• Cons: More complex.

Recursive DFS wins for elegance!

Additional Examples and Edge Cases

• []: 0.
• [1]: 0.
• [1,2]: 2.

Recursive DFS handles them all!

Complexity Recap

• Recursive DFS: Time O(n), Space O(h).
• Iterative BFS: Time O(n), Space O(n).

Recursive DFS’s the simplicity champ!

Key Takeaways

• Recursive DFS: Tilt tracking—learn at Python Basics!
• Iterative BFS: Level processing.
• Trees: Tilts are fun.
• Python: Recurse or iterate, your pick!

Final Thoughts: Calculate That Tilt!

LeetCode 563: Binary Tree Tilt in Python is a delightful tree challenge. Recursive DFS with tilt tracking is your fast track, while iterative BFS offers a thorough twist. Want more? Try LeetCode 104: Maximum Depth or LeetCode 543: Diameter of Binary Tree. Ready to tilt? Head to Solve LeetCode 563 on LeetCode and measure that tilt today!