Binary Tree Tilt - Practice Coding Problems

Binary Tree Tilt - Problem

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.

Input & Output

Example 1 — Simple Tree

$ Input: root = [1,2,3]

› Output: 1

💡 Note: Node 2: tilt = |0-0| = 0, Node 3: tilt = |0-0| = 0, Node 1: tilt = |2-3| = 1. Total tilt = 0 + 0 + 1 = 1

Example 2 — Larger Tree

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

› Output: 15

💡 Note: Leaf nodes have tilt 0. Node 2: |3-5|=2, Node 9: |0-7|=7, Node 4: |10-16|=6. Total = 2+7+6 = 15

Example 3 — Single Node

$ Input: root = [21]

› Output: 0

💡 Note: Single node has no children, so left sum = 0, right sum = 0, tilt = |0-0| = 0

Constraints

The number of nodes in the tree is in the range [0, 10⁴]
-1000 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes [1,2,3]

Calculate Tilts

For each node, find |left_sum - right_sum|

Sum Tilts

Total tilt = sum of all individual node tilts

Key Takeaway

🎯 Key Insight: Use DFS post-order traversal to calculate subtree sums and accumulate tilts in a single pass

Asked in

f Facebook 12 a Amazon 8 M Microsoft 6

The optimal approach uses DFS to calculate subtree sums and accumulate tilts in a single traversal. Each node computes the absolute difference between left and right subtree sums while returning its total subtree sum to the parent. Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Optimal DFS - Single Pass	O(n)	O(h)	Calculate subtree sums and tilts in one DFS traversal
Brute Force - Separate Sum Calculations	O(n²)	O(h)	Calculate subtree sums separately for each node

Optimal DFS - Single Pass — Algorithm Steps

Step 1: Start DFS from root
Step 2: For each node, get left and right subtree sums
Step 3: Calculate tilt and add to global sum
Step 4: Return current subtree sum to parent

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Visit nodes in post-order, calculating subtree sums

Tilt Calculation

For each node, compute tilt and add to total

Return Sum

Return subtree sum to parent node

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int totalTilt = 0;

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int dfs(struct TreeNode* node) {
    if (!node) return 0;
    
    int leftSum = dfs(node->left);
    int rightSum = dfs(node->right);
    
    int tilt = abs(leftSum - rightSum);
    totalTilt += tilt;
    
    return node->val + leftSum + rightSum;
}

int solution(struct TreeNode* root) {
    totalTilt = 0;
    dfs(root);
    return totalTilt;
}

int main() {
    // For simplicity in C, using a fixed test case
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    
    printf("%d\n", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in DFS traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimal DFS - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler