Skip to main content

Post Order Processing

or Bottom up recursion

Traverse​

563. Binary Tree Tilt​

Easy·

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. The tilt of the entire tree is the sum of all node tilts.

2 Approaches
FIG. BINARY TREE TILT● INTERACTIVE
visualization loads as you reach it
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·

Check if a binary tree is height-balanced. A height-balanced tree is one where the left and right subtrees of every node differ in height by no more than 1.

2 Approaches
FIG. BALANCED BINARY TREE● INTERACTIVE
visualization loads as you reach it
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·

Check if a binary tree follows the children sum property. In this property, the sum of values of the left child and right child should be equal to the value of their parent node for all nodes.

2 Approaches
FIG. CHILDREN SUM PROPERTY● INTERACTIVE
visualization loads as you reach it
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·

Count the number of nodes whose value is equal to the sum of the values of their descendants. A descendant of a node is any node that is on the path from the node to a leaf.

2 Approaches
FIG. COUNT NODES EQUAL TO SUM OF DESCENDANTS● INTERACTIVE
visualization loads as you reach it
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·

Find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

2 Approaches
FIG. MOST FREQUENT SUBTREE SUM● INTERACTIVE
visualization loads as you reach it
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·

The diameter is the length of the longest path between any two nodes, which may or may not pass through the root. At each node, the longest path through it is left_height + right_height. A single post-order recursion returns each node's height while tracking the best diameter seen so far.

FIG. DIAMETER OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
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·

Collect and remove leaves layer by layer until the tree is empty. The key insight is that a node's "collection layer" equals its height (distance to its deepest leaf). A post-order recursion computes each node's height and groups node values by that height, so all nodes removed together share the same height.

FIG. FIND LEAVES OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
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·

A univalue subtree is one where every node has the same value. A post-order recursion returns whether the subtree rooted at a node is univalue: it is, when the node matches each existing child and both child subtrees are themselves univalue. Each time that holds, the running count is incremented.

FIG. COUNT UNIVALUE SUBTREES● INTERACTIVE
visualization loads as you reach it
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

2265. Count Nodes Equal to Average of Subtree​

Medium·
2 Approaches
FIG. COUNT NODES EQUAL TO AVERAGE OF SUBTREE● INTERACTIVE
visualization loads as you reach it
def averageOfSubtree(self, root: TreeNode) -> int:
def rec(node):
if not node:
return 0, 0, 0
if not node.left and not node.right:
return 1, node.val, 1
left_count, left_total, left_ans = rec(node.left)
right_count, right_total, right_ans = rec(node.right)
count = 1 + left_count + right_count
total = node.val + left_total + right_total
ans = left_ans + right_ans
if count:
ans += total // count == node.val
return count, total, ans
 
return rec(root)[2]

1120. Maximum Average Subtree​

Medium·
2 Approaches
FIG. MAXIMUM AVERAGE SUBTREE● INTERACTIVE
visualization loads as you reach it
# 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 maximumAverageSubtree(self, root: Optional[TreeNode]) -> float:
def rec(node):
nonlocal maxi
if not node:
return 0, 0
left_count, left_total = rec(node.left)
right_count, right_total = rec(node.right)
count = 1 + left_count + right_count
total = node.val + left_total + right_total
maxi = max(maxi, total / count)
return count, total
 
maxi = 0
rec(root)
return maxi

2331. Evaluate Boolean Binary Tree​

Easy·
2 Approaches
FIG. EVALUATE BOOLEAN BINARY TREE● INTERACTIVE
visualization loads as you reach it
def evaluateTree(self, root: TreeNode | None) -> bool:
def rec(node):
if not node.left and not node.right:
return bool(node.val)
left = rec(node.left)
right = rec(node.right)
return left & right if node.val == 3 else left | right
 
return rec(root)

LCA and its Variants​

236. Lowest Common Ancestor of a Binary Tree​

Medium·
3 Approaches
FIG. LOWEST COMMON ANCESTOR RECURSIVE● INTERACTIVE
visualization loads as you reach it
def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
def rec(node):
nonlocal lca
if not node:
return 0
left = rec(node.left) if node.left else 0
right = rec(node.right) if node.right else 0
found = left + right + int(node == p) + int(node == q)
if not lca and found == 2:
lca = node
return found
 
lca = None
rec(root)
return lca

1644. Lowest Common Ancestor of a Binary Tree II​

Medium·
2 Approaches
FIG. LCA BINARY TREE II RECURSIVE● INTERACTIVE
visualization loads as you reach it
def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
def rec(node):
nonlocal lca
if not node:
return 0
left = rec(node.left) if node.left else 0
right = rec(node.right) if node.right else 0
found = left + right + int(node == p) + int(node == q)
if not lca and found == 2:
lca = node
return found
 
lca = None
rec(root)
return lca

1676. Lowest Common Ancestor of a Binary Tree IV​

Medium·
2 Approaches
FIG. LCA BINARY TREE IV RECURSIVE● INTERACTIVE
visualization loads as you reach it
def lowestCommonAncestor(self, root: "TreeNode", nodes: "List[TreeNode]") -> "TreeNode":
def rec(node):
nonlocal lca
if not node:
return 0
left = rec(node.left) if node.left else 0
right = rec(node.right) if node.right else 0
found = left + right + int(node in nodes)
if not lca and found == len(nodes):
lca = node
return found
 
nodes = set(nodes)
lca = None
rec(root)
return lca

1650. Lowest Common Ancestor of a Binary Tree III​

Medium·
3 Approaches
FIG. LOWEST COMMON ANCESTOR III CLIMB THEN DFS● INTERACTIVE
visualization loads as you reach it
def lowestCommonAncestor(self, p: "Node", q: "Node") -> "Node":
root = p
while root.parent:
root = root.parent
 
def lowestCommonAncestor(node):
nonlocal lca
if not node:
return 0
left = lowestCommonAncestor(node.left) if node.left else 0
right = lowestCommonAncestor(node.right) if node.right else 0
found = left + right + int(node == p) + int(node == q)
if not lca and found == 2:
lca = node
return found
 
lca = None
lowestCommonAncestor(root)
return lca

1740. Find Distance in a Binary Tree​

Medium·
2 Approaches
FIG. FIND DISTANCE IN A BINARY TREE RECURSIVE● INTERACTIVE
visualization loads as you reach it
def findDistance(self, root: TreeNode | None, p: int, q: int) -> int:
def rec(node, depth):
nonlocal lca, p_depth, q_depth, lca_depth
if not node:
return 0
left = rec(node.left, depth + 1)
right = rec(node.right, depth + 1)
found = left + right + int(node.val == p) + int(node.val == q)
if not lca and found == 2:
lca = node
lca_depth = depth
if node.val == p:
p_depth = depth
if node.val == q:
q_depth = depth
return found
 
p_depth = q_depth = lca_depth = -1
lca = None
rec(root, 0)
return p_depth + q_depth - 2 * lca_depth

2509. Cycle Length Queries in a Tree​

Hard·
3 Approaches
class Solution:
def cycleLengthQueries(self, n: int, queries: list[list[int]]) -> list[int]:
"""TLE"""
 
def rec(node, depth):
nonlocal lca, p_depth, q_depth, lca_depth
if node >= 2**n:
return 0
left = rec(2 * node, depth + 1)
right = rec(2 * node + 1, depth + 1)
found = left + right + int(node == p) + int(node == q)
if not lca and found == 2:
lca = node
lca_depth = depth
if node == p:
p_depth = depth
if node == q:
q_depth = depth
return found
 
result = []
for p, q in queries:
p_depth = q_depth = lca_depth = -1
lca = None
rec(1, 0)
result.append(p_depth + q_depth - 2 * lca_depth + 1)
return result

1257. Smallest Common Region​

Medium·
2 Approaches
FIG. SMALLEST COMMON REGION ANCESTOR SET● INTERACTIVE
visualization loads as you reach it
class Solution:
def findSmallestRegion(self, regions: list[list[str]], region1: str, region2: str) -> str:
parents = {}
for parent, *child in regions:
for c in child:
parents[c] = parent
ancestors = set()
root = region1
while root:
ancestors.add(root)
root = parents.get(root, None)
while region2 not in ancestors:
region2 = parents.get(region2, None)
return region2

1123. Lowest Common Ancestor of Deepest Leaves​

Medium·
2 Approaches
FIG. LCA DEEPEST LEAVES TWO PASS● INTERACTIVE
visualization loads as you reach it
def lcaDeepestLeaves(self, root: TreeNode | None) -> TreeNode | None:
def dfs(node, depth):
nonlocal max_depth, max_depth_nodes
if not node:
return
if max_depth < depth:
max_depth = depth
max_depth_nodes = 0
if max_depth == depth:
max_depth_nodes += 1
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
 
max_depth = max_depth_nodes = 0
dfs(root, 0)
 
def lowestCommonAncestor(node, depth):
nonlocal lca
if not node:
return 0
left = lowestCommonAncestor(node.left, depth + 1) if node.left else 0
right = lowestCommonAncestor(node.right, depth + 1) if node.right else 0
found = left + right + int(depth == max_depth)
if not lca and found == max_depth_nodes:
lca = node
return found
 
lca = None
lowestCommonAncestor(root, 0)
return lca

865. Smallest Subtree with all the Deepest Nodes​

Medium·
2 Approaches
FIG. SUBTREE ALL DEEPEST TWO PASS● INTERACTIVE
visualization loads as you reach it
def subtreeWithAllDeepest(self, root: TreeNode | None) -> TreeNode | None:
def dfs(node, depth):
nonlocal max_depth, max_depth_nodes
if not node:
return
if max_depth < depth:
max_depth = depth
max_depth_nodes = 0
if max_depth == depth:
max_depth_nodes += 1
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
 
max_depth = max_depth_nodes = 0
dfs(root, 0)
 
def lowestCommonAncestor(node, depth):
nonlocal lca
if not node:
return 0
left = lowestCommonAncestor(node.left, depth + 1) if node.left else 0
right = lowestCommonAncestor(node.right, depth + 1) if node.right else 0
found = left + right + int(depth == max_depth)
if not lca and found == max_depth_nodes:
lca = node
return found
 
lca = None
lowestCommonAncestor(root, 0)
return lca

Manipulate Tree​

Transform to Sum Tree​

Easy·

Transform a binary tree into a sum tree where each node contains the sum of left and right subtrees in the original tree.

2 Approaches
FIG. TRANSFORM TO SUM TREE● INTERACTIVE
visualization loads as you reach it
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)