Skip to main content

Height, Path, Views

Height​

104. Maximum Depth of Binary Tree​

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. An empty tree has depth 0, a single node has depth 1.

3 Approachesclick to switch
FIG. MAXIMUM DEPTH OF BINARY TREE● 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 one frame per level, so it never exceeds the tree's height h.
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·

Find the minimum depth from the root to any leaf node. The minimum depth is the shortest path from root to leaf.

3 Approachesclick to switch
FIG. MINIMUM DEPTH RECURSIVE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once, doing constant work per call.
Space
O(h)
  • The recursion call stack grows one frame per level, up to the tree height h.
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·

Determine if a binary tree has a root-to-leaf path whose sum equals the given target value. A leaf is a node with no children.

3 Approachesclick to switch
FIG. PATH SUM● 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 holds at most h frames, one per level from root down to the current leaf.
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·

Find all root-to-leaf paths where the sum equals the target value. Return all valid paths as a list of lists containing node values.

3 Approachesclick to switch
FIG. PATH SUM II● INTERACTIVE
visualization loads as you reach it
Time
O(n * h)
  • dfs visits each of the n nodes once, but every leaf match calls deepcopy(path), which costs O(h) since path holds one value per level of the current root-to-leaf chain.
Space
O(n * h)
  • The recursion stack is O(h) deep, but result can hold up to n copied paths, each up to length h, in the worst case.
from copy import deepcopy
 
 
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·

Return all root-to-leaf paths in a binary tree as strings, where each path shows the values connected by "->".

3 Approachesclick to switch
FIG. BINARY TREE PATHS● INTERACTIVE
visualization loads as you reach it
Time
O(n * h)
  • dfs visits each of the n nodes once, but at every leaf deepcopy(path) copies the current path, whose length is bounded by the tree height h, giving O(n * h) overall.
Space
O(n * h)
  • The recursion stack and path are bounded by h, and result stores a deep copy of a path (length up to h) for each of up to n leaves.
from copy import deepcopy
 
 
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]

129. Sum Root to Leaf Numbers​

Medium·

Each root-to-leaf path spells a decimal number (most significant digit at the root). Carry the running value down with cur_decimal = 10 * cur_decimal + node.val, and add it to the total whenever a leaf is reached. This mirrors the binary version (1022), swapping base 2 for base 10.

3 Approachesclick to switch
FIG. SUM ROOT TO LEAF NUMBERS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • recursion visits each node exactly once via recursion(node.left) and recursion(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 (plus the shared nonlocal cur_decimal) goes as deep as the tree, so it holds at most h frames, where h is the tree height.
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·

Each root-to-leaf path spells a binary number (most significant bit at the root). Carry the running value down the path with cur_binary = 2 * cur_binary + node.val, and add it to the total whenever a leaf is reached.

3 Approachesclick to switch
FIG. SUM OF ROOT TO LEAF BINARY NUMBERS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each node is visited once.
Space
O(h)
  • Recursion stack depth equals tree height h.
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·

A root-to-leaf path is pseudo-palindromic if its node values can be rearranged into a palindrome - which happens exactly when at most one digit value appears an odd number of times. Track parity with a bitmask: toggle bit node.val on each step (path ^ (1 << node.val)). At a leaf the path is valid when the mask has at most one bit set, i.e. path & (path - 1) == 0.

2 Approachesclick to switch
FIG. PSEUDO PALINDROMIC PATHS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • recursion visits each of the n nodes exactly once.
Space
O(h)
  • The recursion call stack depth equals tree height h.
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·

The largest |ancestor - descendant| along any root-to-node path equals max - min of the values on that path. Carry the running max_node and min_node down each path; the answer at any point is abs(max_node - min_node), and the overall answer is the largest such value across all paths.

2 Approachesclick to switch
FIG. MAXIMUM DIFFERENCE BETWEEN NODE AND ANCESTOR● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • recursion 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 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·

The left view of a binary tree is the set of nodes visible when the tree is viewed from the left side. In other words, it's the first node at each level when traversing from left to right.

3 Approachesclick to switch
FIG. LEFT VIEW OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs 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. left_view adds one entry per level, at most h, dominated by the same term.
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·

The right view of a binary tree is the set of nodes visible when the tree is viewed from the right side. In other words, it's the last node at each level when traversing from left to right.

3 Approachesclick to switch
FIG. RIGHT VIEW OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the number of nodes - dfs visits every node exactly once, recording the last-seen value at each level.
Space
O(h)
  • h is the tree height - the recursion stack in dfs grows one frame per level, plus right_view holds one entry per level (O(h)), which does not exceed the stack depth.
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·

The top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Each column position should show only the topmost node (closest to root level).

3 Approachesclick to switch
FIG. TOP VIEW OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once; the final list comprehension over range(min_col, max_col + 1) is bounded by the tree's column width, which is at most n.
Space
O(n)
  • The recursion stack goes as deep as the tree (up to n for a skewed tree), and top_view holds at most one entry per column, up to n entries.
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·

The bottom view of a binary tree is the set of nodes visible when the tree is viewed from the bottom. Each column position should show only the bottommost node (farthest from root level).

3 Approachesclick to switch
FIG. BOTTOM VIEW OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once.
Space
O(n)
  • The recursion stack reaches depth up to the tree's height (bounded by n), and bottom_view holds one entry per distinct column, at most n entries.
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·

The boundary of a binary tree is the concatenation of root, left boundary, leaves, and right boundary in counter-clockwise direction.

  • Left boundary: path from root to the left-most node
  • Right boundary: path from root to the right-most node
  • Leaves: all leaf nodes in left-to-right order
2 Approachesclick to switch
FIG. BOUNDARY OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • setLeaves visits every node in the tree once; setLeftBoundary and setRightBoundary each only walk a boundary spine (O(h)), which is dominated by the O(n) leaves pass.
Space
O(h)
  • The deepest recursion is setLeaves, whose call stack grows to the tree's height h.
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