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 Approaches
FIG. MAXIMUM DEPTH OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. MINIMUM DEPTH RECURSIVE● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. PATH SUM● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. PATH SUM II● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. BINARY TREE PATHS● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. SUM ROOT TO LEAF NUMBERS● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. SUM OF ROOT TO LEAF BINARY NUMBERS● INTERACTIVE
visualization loads as you reach it
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

988. Smallest String Starting From Leaf​

Medium·

Each node value 0..25 maps to a letter via chr(ord('a') + node.val). Walk root-to-leaf collecting letters, and at every leaf reverse the collected path to get the leaf-to-root word. Keep the lexicographically smallest word seen.

3 Approaches
FIG. SMALLEST STRING STARTING FROM LEAF● 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 smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
def rec(node):
nonlocal ans
if not node:
return
path.append(chr(ord("a") + node.val))
if not node.left and not node.right:
word = "".join(path[::-1])
ans = ans or word
ans = min(ans, word)
rec(node.left)
rec(node.right)
path.pop()
 
path = []
ans = None
rec(root)
return ans

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 Approaches
FIG. PSEUDO PALINDROMIC PATHS● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. MAXIMUM DIFFERENCE BETWEEN NODE AND ANCESTOR● INTERACTIVE
visualization loads as you reach it
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)

1448. Count Good Nodes in Binary Tree​

Medium·

A node is good when nothing on the path from the root down to it is strictly larger. Only the running maximum of that path matters, so carry maxi down as you descend and compare each node against it. Ties count: the test is node.val >= maxi.

3 Approaches
FIG. COUNT GOOD NODES IN BINARY TREE● 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 goodNodes(self, root: TreeNode) -> int:
def rec(node, maxi):
if not node:
return 0
left = rec(node.left, max(maxi, node.val)) if node.left else 0
right = rec(node.right, max(maxi, node.val)) if node.right else 0
return left + right + int(node.val >= maxi)
 
return rec(root, root.val)

1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree​

Medium·

Decide whether arr spells out a complete root-to-leaf path. Two things must hold together: the values have to match level by level from the root, and the run has to end exactly on a leaf at arr's last index - a matching prefix that stops mid-tree, or a leaf reached too early, is not valid.

3 Approaches
FIG. VALID SEQUENCE FROM ROOT TO LEAVES PATH● INTERACTIVE
visualization loads as you reach it
def isValidSequence(self, root: TreeNode | None, arr: list[int]) -> bool:
def rec(node, depth):
if not node:
return False
if depth >= len(arr) or node.val != arr[depth]:
return False
if not node.left and not node.right and depth == len(arr) - 1:
return True
left = rec(node.left, depth + 1)
right = rec(node.right, depth + 1)
return left or right
 
return rec(root, 0)

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 Approaches
FIG. LEFT VIEW OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. RIGHT VIEW OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. TOP VIEW OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. BOTTOM VIEW OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
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 Approaches
FIG. BOUNDARY OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
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