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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Tree Tilt

Number: 563

Difficulty: Easy

Paid? No

Companies: Indeed

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 defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. If a node lacks a left or right child, the missing side is treated as having a sum of 0.

Key Insights

  • Use a Depth-First Search (DFS) with post-order traversal to compute the sum of each subtree.
  • While returning the sum of each subtree, calculate the tilt for the current node by taking the absolute difference between the left and right subtree sums.
  • Accumulate the tilt values in a global or outer-scope variable.
  • The problem is solved in one traversal of the tree.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree since each node is visited exactly once. Space Complexity: O(h), where h is the height of the tree, due to the recursion stack (in the worst case O(n) for an unbalanced tree).

Solution

We adopt a recursive DFS strategy using post-order traversal. The recursion works as follows:

  1. Recursively obtain the sum of values from the left subtree.
  2. Recursively obtain the sum of values from the right subtree.
  3. Compute the tilt of the current node as the absolute difference between these two sums.
  4. Add the computed tilt to a global accumulator.
  5. Return the total sum of the current subtree (node's value plus left and right subtree sums).

This approach ensures that while computing the sum for any subtree, the tilt for its root is computed correctly and accumulated.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val    # value of the node
        self.left = left  # left child
        self.right = right  # right child

class Solution:
    def findTilt(self, root: TreeNode) -> int:
        self.totalTilt = 0  # global accumulator for all nodes' tilts
        
        def dfs(node):
            # Base case: If the node is None, return sum = 0.
            if not node:
                return 0
            # Recursively calculate sum of left subtree.
            leftSum = dfs(node.left)
            # Recursively calculate sum of right subtree.
            rightSum = dfs(node.right)
            # Current node's tilt is the absolute difference between leftSum and rightSum.
            currentTilt = abs(leftSum - rightSum)
            # Accumulate the tilt.
            self.totalTilt += currentTilt
            # Return the total sum including the current node.
            return node.val + leftSum + rightSum
        
        dfs(root)
        return self.totalTilt
← Back to All Questions