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.

Description Hints 4 Solution Video 13:20

563. Binary Tree Tilt

Easy66.2% acceptance3 companies

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

Asked at 3 companies

Indeed Amazon Meta

Topics

Hints open one at a time

Hint 1

Don't think too much, this is an easy problem. Take some small tree as an example.

Hint 2

Can a parent node use the values of its child nodes? How will you implement it?

Hint 3

May be recursion and tree traversal can help you in implementing.

Hint 4

What about postorder traversal, using values of left and right childs?

13:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution