Skip to main content

Height, Path, Views

Height​

What's the difference between Depth and Height?

104. Maximum Depth of Binary Tree​

Explanation

Solutions:
Visualize
def maxDepth(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0
left_depth = dfs(node.left)
right_depth = dfs(node.right)
return 1 + max(left_depth, right_depth)
 
return dfs(root)

111. Minimum Depth of Binary Tree​

Easy·

Explanation

Solutions:
Visualize
def minDepth(self, root: Optional[TreeNode]) -> int:
def dfs(node):
nonlocal mini, depth
if not node:
return 0
depth += 1
if not node.left and not node.right:
mini = min(mini, depth)
dfs(node.left)
dfs(node.right)
depth -= 1
 
mini = float("inf")
depth = 0
dfs(root)
return mini if mini != float("inf") else 0

Path​

112. Path Sum​

Easy·

Explanation

Solutions:
Visualize
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node, total):
if not node:
return False
total += node.val
if not node.left and not node.right:
return total == targetSum
return dfs(node.left, total) or dfs(node.right, total)
 
return dfs(root, 0) if root else False

113. Path Sum II​

Medium·

Explanation

Solutions:
Visualize
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def dfs(node):
nonlocal path_sum
if node:
path_sum += node.val
path.append(node.val)
 
if not node.left and not node.right and path_sum == targetSum:
result.append(deepcopy(path))
 
dfs(node.left)
dfs(node.right)
 
path.pop()
path_sum -= node.val
 
path = []
path_sum = 0
result = []
dfs(root)
return result

257. Binary Tree Paths​

Easy·

Explanation

Solutions:
Visualize
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def dfs(node):
if node:
path.append(str(node.val))
if not node.left and not node.right:
result.append(deepcopy(path))
dfs(node.left)
dfs(node.right)
path.pop()
 
path = []
result = []
dfs(root)
return ["->".join(root_to_leaf) for root_to_leaf in result]

Root to leaf paths sum​

Medium·

Explanation

Solutions:
Visualize
def treePathSum(self, root):
def dfs(node):
nonlocal path, total
if node:
path = path * 10 + node.data
if not node.left and not node.right:
total += path
dfs(node.left)
dfs(node.right)
path = (path - node.data) // 10
 
path = total = 0
dfs(root)
return total

129. Sum Root to Leaf Numbers​

Medium·

Explanation

Solutions:
Visualize
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def recursion(node):
nonlocal total, cur_decimal
if node:
cur_decimal = 10 * cur_decimal + node.val
if not node.left and not node.right:
total += cur_decimal
recursion(node.left)
recursion(node.right)
cur_decimal //= 10
 
cur_decimal = total = 0
recursion(root)
return total

1022. Sum of Root To Leaf Binary Numbers​

Easy·

Explanation

Solutions:
Visualize
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
def recursion(node):
nonlocal total, cur_binary
if node:
cur_binary = 2 * cur_binary + node.val
if not node.left and not node.right:
total += cur_binary
recursion(node.left)
recursion(node.right)
cur_binary //= 2
 
cur_binary = total = 0
recursion(root)
return total

1457. Pseudo-Palindromic Paths in a Binary Tree​

Medium·

Explanation

Solutions:
Visualize
def pseudoPalindromicPaths(self, root: Optional[TreeNode]) -> int:
def recursion(node, path):
nonlocal ans
if node:
path = (path) ^ (1 << node.val)
if not node.left and not node.right:
ans += path & (path - 1) == 0
recursion(node.left, path) if node.left else None
recursion(node.right, path) if node.right else None
 
ans = 0
recursion(root, 0)
return ans

1026. Maximum Difference Between Node and Ancestor​

Medium·

Explanation

Solutions:
Visualize
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
def recursion(node, max_node, min_node):
if not node:
return 0
max_node = max(max_node, node.val)
min_node = min(min_node, node.val)
 
left = recursion(node.left, max_node, min_node)
right = recursion(node.right, max_node, min_node)
return max(left, right, abs(max_node - min_node))
 
return recursion(root, root.val, root.val)

Views​

Left View of Binary Tree​

Easy·

Explanation

Solutions:
Visualize
def LeftView(self, root):
def dfs(node, level):
if not node:
return
if level not in left_view:
left_view[level] = node.data
dfs(node.left, level + 1)
dfs(node.right, level + 1)
 
left_view = {}
dfs(root, 0)
return list(left_view.values())

Right View of Binary Tree​

Easy·

Explanation

Solutions:
Visualize
def rightView(self, root):
def dfs(node, level):
if not node:
return
right_view[level] = node.data
dfs(node.left, level + 1)
dfs(node.right, level + 1)
 
right_view = {}
dfs(root, 0)
return list(right_view.values())

Top View of Binary Tree​

Medium·

Explanation

Solutions:
Visualize
def topView(self, root):
def dfs(node, level, col):
nonlocal min_col, max_col
if not node:
return
min_col, max_col = min(min_col, col), max(max_col, col)
if col not in top_view or level < top_view[col][1]:
top_view[col] = node.data, level
dfs(node.left, level + 1, col - 1)
dfs(node.right, level + 1, col + 1)
 
min_col, max_col = float("inf"), -float("inf")
top_view = {}
dfs(root, 0, 0)
return [top_view[i][0] for i in range(min_col, max_col + 1)]

Bottom View of Binary Tree​

Medium·

Explanation

Solutions:
Visualize
def bottomView(self, root):
def dfs(node, level, col):
nonlocal min_col, max_col
if not node:
return
min_col, max_col = min(min_col, col), max(max_col, col)
if col not in bottom_view or level >= bottom_view[col][1]:
bottom_view[col] = node.data, level
dfs(node.left, level + 1, col - 1)
dfs(node.right, level + 1, col + 1)
 
min_col, max_col = float("inf"), -float("inf")
bottom_view = {}
dfs(root, 0, 0)
return [bottom_view[i][0] for i in range(min_col, max_col + 1)]

545. Boundary of Binary Tree​

Medium·

Explanation

Solutions:
Visualize
def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
def setLeftBoundary(node):
if not node:
return
boundary.append(node.val) if not is_leaf(node) else None
setLeftBoundary(node.left)
setLeftBoundary(node.right) if not node.left else None
 
def setRightBoundary(node):
if not node:
return
setRightBoundary(node.right)
setRightBoundary(node.left) if not node.right else None
boundary.append(node.val) if not is_leaf(node) else None
 
def setLeaves(node):
if not node:
return
if is_leaf(node) and node != root:
boundary.append(node.val)
setLeaves(node.left)
setLeaves(node.right)
 
is_leaf = lambda node: not node.left and not node.right
 
boundary = [root.val]
setLeftBoundary(root.left)
setLeaves(root)
setRightBoundary(root.right)
return boundary