Skip to main content

Height, Path, Views

Height​

What's the difference between Depth and Height?

104. Maximum Depth of Binary Tree​

104. Maximum Depth of Binary Tree

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

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​

111. Minimum Depth of Binary Tree

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

112. Path Sum

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

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​

113. Path Sum II

Medium3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

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​

257. Binary Tree Paths

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

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​

Root to leaf paths sum

Medium3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

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

Views​

Left View of Binary Tree​

Left View of Binary Tree

Easy3 solutionsexplanationanalysis2 playgrounds

Explanation

Solutions:

Interactive Visualization

Analysis

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​

Right View of Binary Tree

Easy3 solutionsexplanationanalysis2 playgrounds

Explanation

Solutions:

Interactive Visualization

Analysis

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​

Top View of Binary Tree

Medium3 solutionsexplanationanalysis2 playgrounds

Explanation

Solutions:

Interactive Visualization

Analysis

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​

Bottom View of Binary Tree

Medium3 solutionsexplanationanalysis2 playgrounds

Explanation

Solutions:

Interactive Visualization

Analysis

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​

545. Boundary of Binary Tree

Medium2 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Interactive Visualization

Analysis

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