Skip to main content

Post Order Processing

or Bottom up recursion

Traverse​

563. Binary Tree Tilt​

Easy·

Explanation

Solutions:
Visualize
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​

Easy·

Explanation

Solutions:
Visualize
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​

Medium·

Explanation

Solutions:
Visualize
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​

Medium·

Explanation

Solutions:
Visualize
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​

Medium·

Explanation

Solutions:
Visualize
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]

543. Diameter of Binary Tree​

Easy·

Explanation

Solutions:
Visualize
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def recursion(root):
if root:
nonlocal diameter
left_height = recursion(root.left)
right_height = recursion(root.right)
diameter = max(diameter, left_height + right_height)
return max(left_height, right_height) + 1
return 0
 
diameter = 0
recursion(root)
return diameter

366. Find Leaves of Binary Tree​

Medium·

Explanation

Solutions:
Visualize
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
def recursion(node):
if node:
left_height = recursion(node.left)
right_height = recursion(node.right)
height = max(left_height, right_height) + 1
hm[height].append(node.val)
return height
return 0
 
hm = defaultdict(list)
recursion(root)
return list(hm.values())

250. Count Univalue Subtrees​

Medium·

Explanation

Solutions:
Visualize
def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
def recursion(node):
nonlocal count
if not node:
return True
ans = True
if node.left and node.right:
ans = node.val == node.left.val == node.right.val
elif node.left or node.right:
child = node.left or node.right
ans = node.val == child.val
left = recursion(node.left)
right = recursion(node.right)
count += ans and left and right
return ans
 
count = 0
recursion(root)
return count

Manipulate Tree​

Transform to Sum Tree​

Easy·

Explanation

Solutions:
Visualize
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)