Binary Tree Tilt is an intriguing problem on Leetcode that involves understanding and traversing binary trees. This article presents a comprehensive guide to the Binary Tree Tilt problem and explains various methods to solve it using Python.
Leetcode problem #563 is titled “Binary Tree Tilt” and the problem statement is as follows:
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 the sum of 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 there the node does not have a right child.
Input: root = [1,2,3] Output: 1 Explanation: Tilt of node 1 : |2-3| = 1 Tilt of node 2 : |0-0| = 0 Tilt of node 3 : |0-0| = 0 Sum of every tilt is 1.
Definition of Binary Tree Node
Before we dive into solving the problem, let’s define the structure of a binary tree node:
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right
Approaches to Solve the Problem
1. Depth-First Search (DFS) Recursive Approach
One intuitive way to solve this problem is by employing a depth-first search. We need to calculate the sum of all nodes in the subtree rooted at each node. While doing this, we can also calculate the tilt of each node and accumulate it.
class Solution: def findTilt(self, root: TreeNode) -> int: self.total_tilt = 0 def value_sum(node): if not node: return 0 left_sum = value_sum(node.left) right_sum = value_sum(node.right) tilt = abs(left_sum - right_sum) self.total_tilt += tilt return node.val + left_sum + right_sum value_sum(root) return self.total_tilt
value_sumfunction is a recursive helper function that returns the sum of the values of all nodes in the subtree rooted at
- For each node, calculate the tilt and add it to the
- The base case for the recursive function is when the node is
None, in which case the sum is 0.
The time complexity is O(N), where N is the number of nodes in the binary tree. Each node is visited once. The space complexity is O(H), where H is the height of the tree, due to the recursive call stack.
2. Iterative DFS using Stack
We can also implement the DFS approach iteratively using a stack. This way, we can avoid recursion and have better control over the stack space.
class Solution: def findTilt(self, root: TreeNode) -> int: total_tilt = 0 stack = [(root, False, 0, 0)] while stack: node, visited, left_sum, right_sum = stack.pop() if node: if visited: total_tilt += abs(left_sum - right_sum) else: # Right stack.append((node, True, left_sum, right_sum)) stack.append((node.right, False, 0, 0)) # Left stack.append((node.left, False, 0, 0)) if visited: stack.append((None, True, node.val + left_sum + right_sum, 0)) return total_tilt
- Use a stack to perform DFS. For each node, we store whether we have visited it before along with the sum of its left and right subtrees.
- On visiting a node for the first time, push its children onto the stack.
- When visiting a node that has been visited before, calculate its tilt and add it to the total.
The time complexity is O(N) since each node is visited once. The space complexity is O(N) in the worst case.
In this article, we have explored two approaches to solve the Binary Tree Tilt problem on Leetcode using Python – a recursive depth-first search approach and an iterative depth-first search approach. Both approaches have their own advantages. The recursive approach is more concise and easier to understand, while the iterative approach gives us better control over the stack space. Depending on the constraints and specific requirements, one may choose the approach that is the most appropriate. Additionally, working with trees is a common task in computer science, and understanding these concepts is invaluable for both real-world applications and coding interviews.