We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Tilt

Difficulty: Easy

Problem 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.

Key Insights

  • The tilt of a node can be calculated using the values from its left and right subtrees.
  • A recursive depth-first search (DFS) approach can be used to traverse the tree and calculate both the sum of values and the tilt at each node.
  • The overall tilt can be accumulated during the traversal, allowing for a single pass through the tree.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.

Solution

To solve the problem, we can utilize a recursive depth-first search (DFS) approach. For each node, we calculate the sum of values in its left and right subtrees. Using these sums, we can compute the tilt of the node as the absolute difference between the two sums. We maintain a global variable to accumulate the total tilt as we traverse the tree. The algorithm will use a helper function that returns the sum of values for each subtree.

Code Solutions

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

def findTilt(root):
    total_tilt = 0
    
    def dfs(node):
        nonlocal total_tilt
        if not node:
            return 0
        left_sum = dfs(node.left)    # Recursively sum left subtree
        right_sum = dfs(node.right)   # Recursively sum right subtree
        total_tilt += abs(left_sum - right_sum)  # Calculate tilt for the current node
        return left_sum + right_sum + node.val   # Return total sum including current node value
    
    dfs(root)
    return total_tilt
← Back to All Questions