Binary Tree Tilt

Easy
1874.

Binary Tree Tilt

Binary Tree Tilt is an easy coding problem on depth-first search and trees, asked in Amazon and Meta interviews.

Given the root of a binary tree, return the sum of the tilts of all its nodes.

The tilt of a node is the absolute difference between the sum of all values in its left subtree and the sum of all values in its right subtree. A missing subtree has sum 0, so a leaf has tilt 0.

Example 1

Input
root = [1,2,3]
Output
1
Explanation
The leaves 2 and 3 have tilt 0; the root has tilt |2 - 3| = 1.

Example 2

Input
root = [4,2,9,3,5,null,7]
Output
15
Explanation
Tilts: 3, 5 and 7 are leaves (0); 2 → |3 - 5| = 2; 9 → |0 - 7| = 7; 4 → |(2+3+5) - (9+7)| = 6. Total 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, 1000] (LeetCode allows 10^4; lowered here so the total tilt provably fits in a 32-bit integer)
  • -1000 <= Node.val <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findTilt = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Tilt — Solution in Python, Java & C++

Binary Tree Tilt solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Binary Tree Tilt is an easy coding problem on depth-first search and trees, asked in Amazon and Meta interviews.

  • Difficulty: Easy
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the root of a binary tree, return the sum of the tilts of all its nodes.

The tilt of a node is the absolute difference between the sum of all values in its left subtree and the sum of all values in its right subtree. A missing subtree has sum 0, so a leaf has tilt 0.

Example 1

Input: root = [1,2,3]
Output: 1
Explanation: The leaves 2 and 3 have tilt 0; the root has tilt |2 - 3| = 1.

Example 2

Input: root = [4,2,9,3,5,null,7]
Output: 15
Explanation: Tilts: 3, 5 and 7 are leaves (0); 2 → |3 - 5| = 2; 9 → |0 - 7| = 7; 4 → |(2+3+5) - (9+7)| = 6. Total 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, 1000] (LeetCode allows 10^4; lowered here so the total tilt provably fits in a 32-bit integer)
  • -1000 <= Node.val <= 1000

Hints for Binary Tree Tilt

  1. Hint 1

    A node's tilt needs the sums of its two subtrees — information that flows up from the children.

  2. Hint 2

    Recomputing a subtree's sum for every ancestor costs O(n^2) on a chain.

  3. Hint 3

    Let one post-order helper return its subtree's sum while adding |leftSum - rightSum| to a running total.

How to solve Binary Tree Tilt

Subtree sums combine bottom-up: sum(node) = node.val + sum(left) + sum(right). A post-order walk that returns each subtree's sum has both children's sums in hand at every node — exactly what its tilt needs.

Approach

  1. Define sum(null) = 0.
  2. At a node, compute l = sum(left) and r = sum(right).
  3. Add |l - r| to the running total.
  4. Return node.val + l + r.
  5. Call sum(root) and return the total.

Why it works

Each node's tilt is added exactly once — when its own call has both subtree sums — and each subtree sum is computed exactly once, by the call at that subtree's root, so the walk is linear.

Complexity

  • Time — O(n)
  • Space — O(h) recursion depth

Pitfalls

  • The tilt uses the sums of whole subtrees, not just the two children's values.
  • Return the subtree sum from the helper, not the tilt — the parent needs the sum.
  • An empty tree has total tilt 0.

Reference solution

Python

from typing import Optional

def findTilt(root: Optional[TreeNode]) -> int:
    total = 0

    def subtree_sum(node):
        nonlocal total
        if node is None:
            return 0
        l = subtree_sum(node.left)
        r = subtree_sum(node.right)
        total += abs(l - r)
        return node.val + l + r

    subtree_sum(root)
    return total

Java

public static int findTilt(TreeNode root) {
    int[] total = new int[1];
    tiltSum(root, total);
    return total[0];
}

static int tiltSum(TreeNode node, int[] total) {
    if (node == null) return 0;
    int l = tiltSum(node.left, total);
    int r = tiltSum(node.right, total);
    total[0] += Math.abs(l - r);
    return node.val + l + r;
}

C++

int tiltSum(TreeNode* node, int& total) {
    if (!node) return 0;
    int l = tiltSum(node->left, total);
    int r = tiltSum(node->right, total);
    total += abs(l - r);
    return node->val + l + r;
}

int findTilt(TreeNode* root) {
    int total = 0;
    tiltSum(root, total);
    return total;
}

JavaScript

var findTilt = function(root) {
    var total = { value: 0 };
    tiltSum(root, total);
    return total.value;
};

var tiltSum = function(node, total) {
    if (node === null) return 0;
    var l = tiltSum(node.left, total);
    var r = tiltSum(node.right, total);
    total.value += Math.abs(l - r);
    return node.val + l + r;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals