Binary Tree Tilt - Solution & Explanation

Q: Is Binary Tree Tilt easy or hard?

Binary Tree Tilt is categorized as an Easy problem on LeetCode. The challenge mainly involves understanding post-order traversal and combining subtree sum computation with tilt calculation in a single DFS pass.

Q: Binary Tree Tilt Python/Java solution

In Python or Java, implement a recursive helper function that returns subtree sums while updating a global tilt variable. The logic is identical across languages: perform post-order traversal, compute the tilt at each node, and return the subtree sum.

Q: How to solve Binary Tree Tilt in O(n)?

Use a post-order DFS that returns the sum of each subtree. First recursively compute left and right subtree sums, then calculate the node's tilt using abs(leftSum - rightSum). Add this value to a running total and return leftSum + rightSum + node.val to the parent call.

Q: What is the best approach for Binary Tree Tilt?

The best approach uses post-order traversal with Depth-First Search. While computing subtree sums, calculate the tilt at each node as abs(leftSum - rightSum) and accumulate it in a global variable. This ensures each node is processed exactly once, giving O(n) time and O(h) recursion space.

Q: Is Binary Tree Tilt asked at Google/Amazon/Meta?

Binary tree traversal problems like Binary Tree Tilt appear frequently in interviews at companies such as Amazon, Meta, and Google. The problem tests recursion, DFS traversal, and the ability to combine multiple computations in one tree pass.

Q: What data structure is used in Binary Tree Tilt?

The problem uses a binary tree as the primary data structure. The solution relies on Depth-First Search recursion to traverse the tree and compute subtree sums efficiently.

Q: What is the time complexity of Binary Tree Tilt?

The optimal solution runs in O(n) time because every node in the binary tree is visited exactly once during a post-order traversal. Space complexity is O(h) due to the recursion stack, where h is the height of the tree.

EasyTree Depth-First Search Binary Tree19 min readAsked at: Amazon, Meta, Indeed

Practice this problem

Problem Statement

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.

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, 10⁴].
-1000 <= Node.val <= 1000

Approach Overview

Problem Overview: Each node in a binary tree has a tilt defined as the absolute difference between the sum of values in its left subtree and the sum in its right subtree. The task is to compute the total tilt of the entire tree by summing the tilt of every node.

Approach 1: Pre-computed Subtree Sums (O(n²) time, O(h) space)

A straightforward method computes the sum of each subtree every time you calculate a node's tilt. For every node, run a recursive function that traverses the left subtree to compute its sum and another traversal for the right subtree. The tilt for the node becomes abs(leftSum - rightSum), and you repeat the same logic recursively for all nodes. Because subtree sums are recalculated multiple times, the same nodes are visited repeatedly, which leads to O(n²) time in the worst case (for skewed trees). The recursion stack uses O(h) space, where h is the tree height. This approach is useful for understanding the definition of tilt but is inefficient for large trees.

Approach 2: Post-order Traversal (O(n) time, O(h) space)

The optimal strategy computes subtree sums while traversing the tree once using Depth-First Search. A post-order traversal processes the left subtree, then the right subtree, and finally the current node. When returning from recursion, each call provides the total sum of that subtree. At the current node, compute the tilt with abs(leftSum - rightSum) and add it to a global accumulator. Then return leftSum + rightSum + node.val to the parent call. Each node contributes to the calculation exactly once, producing O(n) time complexity with O(h) recursion space. This method naturally fits tree problems where information flows upward during traversal.

This approach works well for any binary tree because subtree results are reused instead of recomputed. The key insight is combining two tasks in a single DFS pass: computing subtree sums and accumulating tilt.

Recommended for interviews: Interviewers expect the post-order DFS solution. The brute-force subtree-sum approach shows that you understand the tilt definition, but the optimized traversal demonstrates your ability to eliminate repeated work and design linear-time tree algorithms.

Approach 1: Post-order Traversal

The idea behind the post-order traversal approach is to calculate the tilt of a node when all its children have been processed. For each node, compute the sum of node values for the left and right subtrees separately, calculate the node's tilt as the absolute difference of these two sums, and then propagate these subtree sums up to the parent node.

The C solution uses a helper function findTiltUtil which computes the sum of subtree node values and the tilt. It takes a pointer to tiltSum which accumulates the total tilt as a side effect.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) where n is the number of nodes, as we visit each node once. Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.

Try this approach in the editor →

Approach 2: Pre-computed Subtree Sums

In this approach, we preprocess the subtree sums for each node iteratively or recursively. Then we use these sums to calculate the tilt for each node in a separate pass through the tree. This separation of concerns can offer cleaner logic and easier maintenance of code.

In this C solution, an initial two-pass approach is refined to a more efficient calculation of both the subtree sums and the tilt within two separate but integrated recursions. This eliminates redundant recalculations.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2) because calculateSubtreeSum might be called multiple times. Space Complexity: O(h).

Try this approach in the editor →

Approach 3: Recursion

We design a function dfs to calculate the sum of nodes in the subtree rooted at the current node. In the dfs function, we first check if the current node is null. If it is, we return 0. Then we recursively call the dfs function to calculate the sum of nodes in the left subtree l and the sum of nodes in the right subtree r. Next, we calculate the tilt of the current node, which is |l - r|, and add it to the answer. Finally, we return the sum of nodes of the current node, which is l + r + root.val.

In the main function, we initialize the answer to 0, then call the dfs function to calculate the tilt of the entire tree and return the answer.

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Post-order Traversal	Time Complexity: O(n) where n is the number of nodes, as we visit each node once. Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.
Pre-computed Subtree Sums	Time Complexity: O(n^2) because calculateSubtreeSum might be called multiple times. Space Complexity: O(h).
Recursion	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Pre-computed Subtree Sums	O(n²)	O(h)	Good for understanding the tilt definition or when learning recursion on trees
Post-order Traversal (DFS)	O(n)	O(h)	Optimal approach for interviews and production solutions

Video Solution

Binary tree Tilt | LeetCode 563 | C++, Java, Python • Knowledge Center • 4,545 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Binary Tree Tilt easy or hard?

Binary Tree Tilt is categorized as an Easy problem on LeetCode. The challenge mainly involves understanding post-order traversal and combining subtree sum computation with tilt calculation in a single DFS pass.

Binary Tree Tilt Python/Java solution

In Python or Java, implement a recursive helper function that returns subtree sums while updating a global tilt variable. The logic is identical across languages: perform post-order traversal, compute the tilt at each node, and return the subtree sum.

How to solve Binary Tree Tilt in O(n)?

Use a post-order DFS that returns the sum of each subtree. First recursively compute left and right subtree sums, then calculate the node's tilt using abs(leftSum - rightSum). Add this value to a running total and return leftSum + rightSum + node.val to the parent call.

What is the best approach for Binary Tree Tilt?

The best approach uses post-order traversal with Depth-First Search. While computing subtree sums, calculate the tilt at each node as abs(leftSum - rightSum) and accumulate it in a global variable. This ensures each node is processed exactly once, giving O(n) time and O(h) recursion space.

Is Binary Tree Tilt asked at Google/Amazon/Meta?

Binary tree traversal problems like Binary Tree Tilt appear frequently in interviews at companies such as Amazon, Meta, and Google. The problem tests recursion, DFS traversal, and the ability to combine multiple computations in one tree pass.

What data structure is used in Binary Tree Tilt?

The problem uses a binary tree as the primary data structure. The solution relies on Depth-First Search recursion to traverse the tree and compute subtree sums efficiently.

What is the time complexity of Binary Tree Tilt?

The optimal solution runs in O(n) time because every node in the binary tree is visited exactly once during a post-order traversal. Space complexity is O(h) due to the recursion stack, where h is the height of the tree.

Ready to solve this problem?

Practice Binary Tree Tilt with our built-in code editor and test cases.

Practice on FleetCode

Find All The Lonely Nodes

Problem Info

DifficultyEasy

Acceptance66.2%

Approaches3

Reading time19 min

Asked at

Amazon Meta Indeed

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Post-order Traversal

Code

Complexity

Approach 2: Pre-computed Subtree Sums

Code

Complexity

Approach 3: Recursion

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents