Domain 1EasyCORE

Binary Tree Tilt

The problem requires calculating the sum of the tilt for all nodes in a binary tree. The tilt of a node is defined as the absolute difference between the sum of values in its left subtree and the sum of values in its right subtree. If a node has no left or right child, the sum for that side is considered 0.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search#Recursion

563. Binary Tree Tilt

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Recursion
FAANG asked: 0
Acceptance rate: 53.2%


Problem Breakdown

The problem requires calculating the sum of the tilt for all nodes in a binary tree. The tilt of a node is defined as the absolute difference between the sum of values in its left subtree and the sum of values in its right subtree. If a node has no left or right child, the sum for that side is considered 0.

Inputs:

  • root: The root node of the binary tree.

Outputs:

  • An integer representing the total tilt of all nodes in the tree.

Implicit Constraints and Edge Cases:

  • The tree can be empty (root is None).
  • Nodes can have negative values.
  • The number of nodes is up to 10,000, so the solution should be efficient in terms of both time and space.

Intuition

A brute-force approach would involve calculating the sum of each subtree for every node, which results in a high time complexity due to repeated calculations. A more efficient approach involves using a single traversal of the tree to compute both the tilt and the sum of values simultaneously.

The key insight is to use a recursive function that returns two values: the total tilt up to the current node and the sum of all node values in the subtree rooted at the current node. This way, we can calculate the tilt for each node while also building up the sum for its parent nodes.

Approach

  1. Recursive Function: Define a helper function calculate_tilt_and_sum that takes a node as input and returns two values:
    • The total tilt of the subtree rooted at the current node.
    • The sum of all node values in the subtree rooted at the current node.
  2. Base Case: If the node is None, return a tilt of 0 and a sum of 0.
  3. Recursive Case:
    • Recursively calculate the tilt and sum for the left and right subtrees.
    • Compute the tilt of the current node as the absolute difference between the sums of its left and right subtrees.
    • The total tilt for the current subtree is the sum of the tilts of its left and right subtrees plus the tilt of the current node.
    • The sum of all node values in the current subtree is the sum of the values of its left and right subtrees plus the value of the current node.
  4. Return Result: Call the helper function on the root node and return the total tilt.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
  • Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case, for a skewed tree, this can be O(n).

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findTilt(root: Optional[TreeNode]) -> int:
    def calculate_tilt_and_sum(node):
        if not node:
            return 0, 0
        
        # Recursively calculate tilt and sum for the left subtree
        left_tilt, left_sum = calculate_tilt_and_sum(node.left)
        
        # Recursively calculate tilt and sum for the right subtree
        right_tilt, right_sum = calculate_tilt_and_sum(node.right)
        
        # Calculate the tilt of the current node
        current_tilt = abs(left_sum - right_sum)
        
        # Total tilt is the sum of tilts from left and right subtrees plus current tilt
        total_tilt = left_tilt + right_tilt + current_tilt
        
        # Sum of all values in the subtree rooted at the current node
        total_sum = left_sum + right_sum + node.val
        
        return total_tilt, total_sum
    
    # Start the recursion from the root
    total_tilt, _ = calculate_tilt_and_sum(root)
    
    return total_tilt

Edge Cases Handled

  • Empty Tree: If the input tree is empty (root is None), the function returns 0 immediately.
  • Negative Node Values: The solution correctly handles nodes with negative values by using absolute differences when calculating tilts.
  • Skewed Trees: The recursive approach efficiently handles trees that are heavily skewed to one side, maintaining a time complexity of O(n) and a space complexity proportional to the height of the tree.