#563

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Tilt

Calculate the sum of the binary tree's node tilts using tree traversal and state tracking.

Problem Statement

Given the root of a binary tree, your task is to calculate the sum of all node tilts in the tree. The tilt of each node is the absolute difference between the sum of values in the left and right subtrees of that node. If a subtree is missing a child, treat the sum of that subtree as zero.

For example, with a binary tree root = [1,2,3], the tilt of node 1 is |2-3| = 1. Nodes without children, such as 2 and 3, will have a tilt of 0. The sum of all tilts is the total tilt of the tree.

Examples

Example 1

Input: root = [1,2,3]

Output: 1

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

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

Example details omitted.

Constraints

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000

Solution Approach

Tree Traversal with Post-Order DFS

To calculate the tilt, perform a post-order depth-first search (DFS) traversal. For each node, first calculate the tilt of its left and right subtrees, then compute the node’s tilt by comparing the sums of the left and right subtrees.

State Tracking for Subtree Sums

While performing the DFS, maintain a running sum of the node's subtree values. The tilt calculation requires these sums, so store the sum of each subtree as you traverse the tree to avoid redundant calculations.

Efficient Summing and Tilt Calculation

The tilt of a node is calculated as the absolute difference between the sum of the left and right subtrees. The tilt values are then accumulated to compute the total tilt for the entire tree.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N)
Space	\mathcal{O}(N)

The time complexity of this approach is \mathcal{O}(N) since we visit each node exactly once during the DFS traversal. The space complexity is also \mathcal{O}(N) due to the space needed to store the recursive call stack during traversal.

What Interviewers Usually Probe

Candidate demonstrates clear understanding of tree traversal techniques.
Candidate can efficiently manage state while performing the DFS.
Candidate is able to articulate the trade-offs between different traversal methods.

Common Pitfalls or Variants

Common pitfalls

Forgetting to track the sum of each subtree, leading to incorrect tilt calculations.
Not properly handling cases where a node has no children, causing incorrect tilt values.
Misunderstanding the problem and trying to calculate the tilt with a more complex traversal.

Follow-up variants

Alter the problem to return the tilt of a subtree rather than the entire tree's tilt.
Extend the problem to handle nodes with more than two children.
Modify the input to be a multi-level list instead of a binary tree representation.

FAQ

What is the tilt of a node in the Binary Tree Tilt problem?

The tilt of a node is the absolute difference between the sum of the values of its left and right subtrees.

How do I calculate the tilt of a node in a binary tree?

To calculate the tilt, traverse the tree using DFS, calculate the sum of each node’s left and right subtrees, and compute their difference.

What’s the primary traversal method used to solve Binary Tree Tilt?

The solution uses a post-order DFS traversal to calculate the tilt of each node and accumulate the total tilt.

How can GhostInterview help with the Binary Tree Tilt problem?

GhostInterview assists by breaking down the traversal and tilt calculation, and guiding you through common pitfalls.

What is the complexity of solving the Binary Tree Tilt problem?

The time complexity is \mathcal{O}(N) and the space complexity is \mathcal{O}(N), where N is the number of nodes in the tree.

terminal

Solution

Solution 1: Recursion

We design a function $\text{dfs}$ to calculate the sum of nodes in the subtree rooted at the current node. In the $\text{dfs}$ function, we first check if the current node is null. If it is, we return 0. Then we recursively call the $\text{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 + \textit{root.val}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree 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: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]) -> int:
            if root is None:
                return 0
            l, r = dfs(root.left), dfs(root.right)
            nonlocal ans
            ans += abs(l - r)
            return l + r + root.val

        ans = 0
        dfs(root)
        return ans

Continue Practicing

#572 subtree of another tree #538 convert bst to greater tree #530 minimum absolute difference in bst