Skip to main content

Post Order Processing

or Bottom up recursion

Traverse​

563. Binary Tree Tilt​

563. Binary Tree Tilt

Easy2 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

def findTilt(self, root: Optional[TreeNode]) -> int:
def dfs(node):
nonlocal tilt
if not node:
return 0
left_total = dfs(node.left)
right_total = dfs(node.right)
tilt += abs(left_total - right_total)
return node.val + left_total + right_total
 
tilt = 0
dfs(root)
return tilt

110. Balanced Binary Tree​

110. Balanced Binary Tree

Easy2 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(node):
if not node:
return True, 0
left_result, left_height = dfs(node.left)
right_result, right_height = dfs(node.right)
 
node_height = 1 + max(left_height, right_height)
if abs(left_height - right_height) > 1:
return False, node_height
return left_result and right_result, node_height
 
return dfs(root)[0]

Children Sum in a Binary Tree​

Children Sum in a Binary Tree

Medium2 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

def isSumProperty(self, root):
def dfs(node):
if not node:
return 0, True
if not node.left and not node.right:
return node.data, True
left_total, left_result = dfs(node.left)
right_total, right_result = dfs(node.right)
child_total = left_total + right_total
return node.data, left_result and right_result and node.data == child_total
 
return dfs(root)[1]

1973. Count Nodes Equal to Sum of Descendants​

Medium2 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

def equalToDescendants(self, root: Optional[TreeNode]) -> int:
def dfs(node):
nonlocal count
if not node:
return 0
left_total = dfs(node.left)
right_total = dfs(node.right)
descendant_total = left_total + right_total
count += descendant_total == node.val
return node.val + descendant_total
 
count = 0
dfs(root)
return count

508. Most Frequent Subtree Sum​

508. Most Frequent Subtree Sum

Medium2 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

import collections
 
 
def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node):
nonlocal max_freq
if not node:
return 0
left_total = dfs(node.left)
right_total = dfs(node.right)
total = node.val + left_total + right_total
frequency[total] += 1
max_freq = max(max_freq, frequency[total])
return total
 
frequency = collections.defaultdict(int)
max_freq = 0
dfs(root)
return [total for total, freq in frequency.items() if freq == max_freq]

Manipulate Tree​

Transform to Sum Tree​

Transform to Sum Tree

Easy2 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

def toSumTree(self, root):
def dfs(node):
if not node:
return 0
left_total = dfs(node.left)
right_total = dfs(node.right)
total = left_total + right_total + node.data
node.data = left_total + right_total
return total
 
dfs(root)