Leetcode – Binary Tree Tilt Solution in Python

Spread the love

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.

Problem Statement

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.

Example:

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

Explanation:

  1. The value_sum function is a recursive helper function that returns the sum of the values of all nodes in the subtree rooted at node.
  2. For each node, calculate the tilt and add it to the total_tilt.
  3. The base case for the recursive function is when the node is None, in which case the sum is 0.

Time Complexity:

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

Explanation:

  1. 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.
  2. On visiting a node for the first time, push its children onto the stack.
  3. When visiting a node that has been visited before, calculate its tilt and add it to the total.

Time Complexity:

The time complexity is O(N) since each node is visited once. The space complexity is O(N) in the worst case.

Conclusion

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.

Leave a Reply