Binary Tree Tilt solution and explanation
9 more videos on this problem
Binary tree Tilt | LeetCode 563 | C++, Java, PythonKnowledge Center · 13:20 · 4K views
Binary Tree Tilt 🔥| Leetcode 563 | Binary TreeAyushi Sharma · 9:22 · 3K views
Binary Tree Tilt | Live Coding with Explanation | Leetcode #563Algorithms Made Easy · 3:22 · 2K views
Binary Tree Tilt | binary tree tilt | leetcode 563 | binary tree | dfs postorderNaresh Gupta · 6:10 · 1K views
Binary Tree Tilt | Leetcode 563 | leetcode solutionEasyLeetcode · 14:52 · 781 views
LeetCode - 563. Binary Tree Tilt | Day 8 December ChallengeAditya Mahajan · 8:17 · 621 views
Binary Tree Tilt | Leetcode 563 | Live coding session 💯💯💯💯 | TC O(n)Coding Decoded · 5:33 · 594 views
Binary Tree Tilt LeetCode 563 Solution using Depth First SearchSuperCode · 7:41 · 510 views
Binary Tree Tilt Leetcode | Leetcode 563 | Leetcode november challengeCode Bashers · 7:23 · 431 views
Binary Tree Tilt | Leetcode Solution 563 | C++,Java Solutions-With ApproachDilip kumar Gangwar · 20:09 · 416 views
The 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.
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 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(n2) 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(n2) 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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def findTilt(self, root: TreeNode) -> int:
self.tilt_sum = 0
def sum_and_tilt(node: TreeNode) -> int:
if not node:
return 0
left = sum_and_tilt(node.left)
right = sum_and_tilt(node.right)
self.tilt_sum += abs(left - right)
return node.val + left + right
sum_and_tilt(root)
return self.tilt_sumclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int tiltSum = 0;
public int findTilt(TreeNode root) {
sumAndTilt(root);
return tiltSum;
}
private int sumAndTilt(TreeNode node) {
if (node == null) return 0;
int left = sumAndTilt(node.left);
int right = sumAndTilt(node.right);
tiltSum += Math.abs(left - right);
return node.val + left + right;
}
}#include <cmath>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int findTilt(TreeNode* root) {
int tiltSum = 0;
sumAndTilt(root, tiltSum);
return tiltSum;
}
int sumAndTilt(TreeNode* node, int& tiltSum) {
if (node == nullptr) return 0;
int left = sumAndTilt(node->left, tiltSum);
int right = sumAndTilt(node->right, tiltSum);
tiltSum += abs(left - right);
return node->val + left + right;
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var findTilt = function(root) {
let tiltSum = 0;
function sumAndTilt(node) {
if (!node) return 0;
let left = sumAndTilt(node.left);
let right = sumAndTilt(node.right);
tiltSum += Math.abs(left - right);
return node.val + left + right;
}
sumAndTilt(root);
return tiltSum;
};#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int findTiltUtil(struct TreeNode* root, int* tiltSum) {
if (root == NULL) return 0;
int leftSum = findTiltUtil(root->left, tiltSum);
int rightSum = findTiltUtil(root->right, tiltSum);
*tiltSum += abs(leftSum - rightSum);
return root->val + leftSum + rightSum;
}
int findTilt(struct TreeNode* root) {
int tiltSum = 0;
findTiltUtil(root, &tiltSum);
return tiltSum;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private int tiltSum = 0;
public int FindTilt(TreeNode root) {
SumAndTilt(root);
return tiltSum;
}
private int SumAndTilt(TreeNode node) {
if (node == null) return 0;
int left = SumAndTilt(node.left);
int right = SumAndTilt(node.right);
tiltSum += Math.Abs(left - right);
return node.val + left + right;
}
}The Python solution involves a recursive closure sum_and_tilt which mutates the state of self.tilt_sum to capture the total tilt progressively during the recursion.
Time Complexity: O(n). Space Complexity: O(h), where h is the height of the tree.
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def calculate_subtree_sum(self, node):
if not node:
return 0
return node.val + self.calculate_subtree_sum(node.left) + self.calculate_subtree_sum(node.right)
def calculate_tilt(self, node):
if not node:
return 0
left_sum = self.calculate_subtree_sum(node.left)
right_sum = self.calculate_subtree_sum(node.right)
left_tilt = self.calculate_tilt(node.left)
right_tilt = self.calculate_tilt(node.right)
return abs(left_sum - right_sum) + left_tilt + right_tilt
def findTilt(self, root):
return self.calculate_tilt(root)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int calculateSubtreeSum(TreeNode node) {
if (node == null) return 0;
return node.val + calculateSubtreeSum(node.left) + calculateSubtreeSum(node.right);
}
private int calculateTilt(TreeNode node) {
if (node == null) return 0;
int leftSum = calculateSubtreeSum(node.left);
int rightSum = calculateSubtreeSum(node.right);
int leftTilt = calculateTilt(node.left);
int rightTilt = calculateTilt(node.right);
return Math.abs(leftSum - rightSum) + leftTilt + rightTilt;
}
public int findTilt(TreeNode root) {
return calculateTilt(root);
}
}#include <cmath>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int calculateSubtreeSum(TreeNode* node) {
if (node == nullptr) return 0;
return node->val + calculateSubtreeSum(node->left) + calculateSubtreeSum(node->right);
}
int calculateTilt(TreeNode* node) {
if (node == nullptr) return 0;
int leftSum = calculateSubtreeSum(node->left);
int rightSum = calculateSubtreeSum(node->right);
int leftTilt = calculateTilt(node->left);
int rightTilt = calculateTilt(node->right);
return abs(leftSum - rightSum) + leftTilt + rightTilt;
}
int findTilt(TreeNode* root) {
return calculateTilt(root);
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
function calculateSubtreeSum(node) {
if (node === null) return 0;
return node.val + calculateSubtreeSum(node.left) + calculateSubtreeSum(node.right);
}
function calculateTilt(node) {
if (node === null) return 0;
let leftSum = calculateSubtreeSum(node.left);
let rightSum = calculateSubtreeSum(node.right);
let leftTilt = calculateTilt(node.left);
let rightTilt = calculateTilt(node.right);
return Math.abs(leftSum - rightSum) + leftTilt + rightTilt;
}
var findTilt = function(root) {
return calculateTilt(root);
};#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int calculateSubtreeSum(struct TreeNode* node) {
if (node == NULL) return 0;
return node->val + calculateSubtreeSum(node->left) + calculateSubtreeSum(node->right);
}
int calculateTilt(struct TreeNode* node) {
if (node == NULL) return 0;
int leftSum = calculateSubtreeSum(node->left);
int rightSum = calculateSubtreeSum(node->right);
int leftTilt = calculateTilt(node->left);
int rightTilt = calculateTilt(node->right);
return abs(leftSum - rightSum) + leftTilt + rightTilt;
}
int findTilt(struct TreeNode* root) {
return calculateTilt(root);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private int CalculateSubtreeSum(TreeNode node) {
if (node == null) return 0;
return node.val + CalculateSubtreeSum(node.left) + CalculateSubtreeSum(node.right);
}
private int CalculateTilt(TreeNode node) {
if (node == null) return 0;
int leftSum = CalculateSubtreeSum(node.left);
int rightSum = CalculateSubtreeSum(node.right);
int leftTilt = CalculateTilt(node.left);
int rightTilt = CalculateTilt(node.right);
return Math.Abs(leftSum - rightSum) + leftTilt + rightTilt;
}
public int FindTilt(TreeNode root) {
return CalculateTilt(root);
}
}This Python solution structures the process with a focus on the use of inner methods to distinctly handle sum and tilt calculations. The recursive flow integrates cleanly with Python's dynamic type system.
Time Complexity: O(n^2). Space Complexity: O(h).
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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function findTilt(root: TreeNode | null): number {
let ans: number = 0;
const dfs = (root: TreeNode | null): number => {
if (!root) {
return 0;
}
const [l, r] = [dfs(root.left), dfs(root.right)];
ans += Math.abs(l - r);
return l + r + root.val;
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findTilt(root *TreeNode) (ans int) {
var dfs func(*TreeNode) int
dfs = func(root *TreeNode) int {
if root == nil {
return 0
}
l, r := dfs(root.Left), dfs(root.Right)
ans += abs(l - r)
return l + r + root.Val
}
dfs(root)
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Post-order Traversal | Time Complexity: O(n). Space Complexity: O(h), where h is the height of the tree. |
| Pre-computed Subtree Sums | Time Complexity: O(n^2). Space Complexity: O(h). |
| Recursion | – |
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 |
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.