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 Approachesclick to switch
FIG. BINARY TREE TILT● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once, accumulating tilt on the way back up.
Space
O(h)
  • The recursion stack goes one frame deep per level, up to the tree height h.
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 Approachesclick to switch
FIG. BALANCED BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits every node exactly once via dfs(node.left) and dfs(node.right), doing O(1) work per node, so total is O(n), where n is the number of nodes.
Space
O(h)
  • The recursion stack goes as deep as the tree, holding at most h frames, where h is the tree height.
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 Approachesclick to switch
FIG. CHILDREN SUM PROPERTY● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each node exactly once.
Space
O(h)
  • The recursion call stack grows with tree height h.
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 Approachesclick to switch
FIG. COUNT NODES EQUAL TO SUM OF DESCENDANTS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once.
Space
O(h)
  • The recursion call stack grows with the tree's height h.
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 Approachesclick to switch
FIG. MOST FREQUENT SUBTREE SUM● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the number of nodes - dfs visits every node exactly once.
Space
O(n)
  • frequency stores up to n distinct subtree sums.
  • The recursion stack in dfs reaches depth h (the tree height), dominated by n.
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
Time
O(n)
  • recursion visits each of the n nodes exactly once, updating diameter on the way back up.
Space
O(h)
  • The recursion stack goes one frame deep per level, up to the tree height h.
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
Time
O(n)
  • n is the number of nodes - recursion visits every node exactly once.
Space
O(n)
  • hm collects every node's value exactly once across all height buckets, up to n values total, which dominates the recursion stack's O(h) depth.
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
Time
O(n)
  • recursion visits each of the n nodes exactly once.
Space
O(h)
  • The recursion stack holds one frame per level on the current path, where h is the tree height.
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 Approachesclick to switch
FIG. COUNT NODES EQUAL TO AVERAGE OF SUBTREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • rec visits each of the n nodes exactly once.
Space
O(h)
  • The recursion stack holds one frame per level on the current path, where h is the tree height.
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 Approachesclick to switch
FIG. MAXIMUM AVERAGE SUBTREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • rec visits every node exactly once, n = number of nodes in the tree; each call does O(1) work combining its children's (count, total).
Space
O(h)
  • No structure is allocated beyond the recursion stack, whose depth is the tree height h (worst case n for a skewed tree, log n for a balanced tree).
# 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

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 Approachesclick to switch
FIG. TRANSFORM TO SUM TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the tree's n nodes exactly once.
Space
O(h)
  • The recursion call stack grows with the tree's height h.
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)