Vultr DocsLatest Content

Binary Tree Tilt

Updated on 14 May, 2025
Binary Tree Tilt header image

Problem Statement

The task is to compute the sum of the tilts for all nodes in a binary tree. A node's tilt is defined as the absolute difference between the sum of the values in its left subtree and the sum of the values in its right subtree. If a node lacks a left or right child, the corresponding subtree sum is considered to be 0. The problem requires calculating the sum of these tilts for the entire tree, starting from its root.

Examples

Example 1

Input:

root = [1,2,3]

Output:

1

Explanation:

Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

Example 2

Input:

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

Output:

15

Explanation:

Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 5 : |0-0| = 0 (no children)
Tilt of node 7 : |0-0| = 0 (no children)
Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5)
Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7)
Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16)
Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15

Example 3

Input:

root = [21,7,14,1,1,2,2,3,3]

Output:

9

Constraints

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000

Approach and Intuition

To solve this problem, you can adopt a recursive depth-first search (DFS) strategy. Here's a step-by-step breakdown of the approach:

  1. Define a recursive function that computes the total sum of all node values for a given subtree. During this computation, calculate the tilt of the current node.

  2. For each node:

    • Recursively calculate the sum of values in the left subtree.
    • Recursively calculate the sum of values in the right subtree.

  3. Compute the tilt for the current node as the absolute difference between the sums obtained from the left and right subtrees.

  4. Accumulate the tilt of the current node to a global variable which keeps track of the sum of all tilts.

  5. Return the sum of node values of the current subtree (to its parent), which is used to compute the tilt at the parent node.

Through this recursive function, each node's tilt is calculated using its children's subtree sums, and simultaneously, these sums are computed and propagated up the tree. This efficient recursion ensures that each node's value is used exactly once for tilt calculation and once for subtree sum computation, leading to an optimal solution with respect to time complexity.

Solutions

  • Java
  • Python
java 
class Solution {
    private int totalTiltValue = 0;

    private int sumValues(TreeNode currentNode) {
        if (currentNode == null)
            return 0;

        int leftValueSum = this.sumValues(currentNode.left);
        int rightValueSum = this.sumValues(currentNode.right);
        int currentTilt = Math.abs(leftValueSum - rightValueSum);
        this.totalTiltValue += currentTilt;

        return currentNode.val + leftValueSum + rightValueSum;
    }

    public int findTilt(TreeNode rootNode) {
        this.totalTiltValue = 0;
        this.sumValues(rootNode);
        return this.totalTiltValue;
    }
}

The provided solution pertains to calculating the tilt of a binary tree. In this tree, each node's tilt is defined as the absolute difference between the sum of all node values in its left subtree and the sum of all node values in its right subtree. The overall tilt of the tree is then the sum of tilts for all nodes.

The Java solution consists of a Solution class which includes a helper function sumValues and the main function findTilt.

  • sumValues:

    • Takes a TreeNode as an argument.
    • Recursively calculates the sum of values in both the left and right subtrees.
    • Computes the tilt for the current node by taking the absolute difference between these sums.
    • Adds this tilt to a global variable totalTiltValue.
    • Returns the sum of the node's value and its left and right subtree sums. This return value assists in calculating the tilt for the node's parent.

  • findTilt:

    • Initializes totalTiltValue to zero.
    • Calls sumValues starting from the rootNode.
    • Returns totalTiltValue, which by the end of execution, holds the total tilt of the binary tree.

The approach is efficient because each node is visited once, yielding a time complexity proportional to the number of nodes in the tree, O(n). The space complexity is O(h), where h is the height of the tree, due to recursive stack space in the worst case when the tree is skewed.

python 
class Solution:
    def calculateTilt(self, root: TreeNode) -> int:
        accumulated_tilt = 0

        def calculateNodeSum(node):
            nonlocal accumulated_tilt

            if node is None:
                return 0

            sum_left = calculateNodeSum(node.left)
            sum_right = calculateNodeSum(node.right)
            current_tilt = abs(sum_left - sum_right)
            accumulated_tilt += current_tilt

            return sum_left + sum_right + node.val

        calculateNodeSum(root)

        return accumulated_tilt

The provided Python solution aims to calculate the tilt of a binary tree, where the tilt of a 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. Here's how the solution works:

  • Define the main class Solution with a method, calculateTilt.
  • Declare a non-local variable, accumulated_tilt, which stores the overall tilt of the tree.
  • Inside calculateTilt, define a nested helper function, calculateNodeSum, which computes the sum of the values for the nodes' subtrees recursively.

Steps to process tilt for each node:

  1. If the current node is None, return a sum of 0, implying no further nodes to process and nothing contributes to the tilt.
  2. Recursively call calculateNodeSum for the left and right child nodes of the current node to get their respective subtree sums.
  3. Calculate the tilt for the current node using the absolute difference between the left and right subtree sums.
  4. Add the current tilt to accumulated_tilt to track the accumulated tilt of the entire tree.
  5. Return the sum of the left subtree, right subtree, and the current node's value, useful for upper recursive calls.

After executing the calculateNodeSum function on the root of the tree, the total tilt is held in accumulated_tilt, which is then returned as the result of the calculateTilt function. Throughout this process, the code utilizes recursion to navigate through each node in the tree and calculate the subtrees' sums and tilts.

Comments

No comments yet.