Skills for tackling LeetCode problems - Tree Depth First Search.
We can use recursion or a stack for iteration to keep track of all the parent nodes while traversing. The space complexity is O(H), where H is the maximum height of the tree.
1. Binary Tree Path Sum
Given a binary tree and a number S, find if the tree has a path from root-to-leaf such that the sum of all the node values of that path equals S.
# Time complexity O(N). Space complexity O(N). N is the total number of nodes.
# class TreeNode:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def has_path(root, S):
if root is None: return False
if root.val == S and root.left is None and root.right is None:
return True
return has_path(root.left, S - root.val) or has_path(root.right, S - root.val)
2. All Path for a Sum
Given a binary tree and a number S, find all paths from root-to-leaf such that the sum of all the node values of each path equals S.
# Time complexity O(N log N). Space complexity O(N log N).
def find_paths(root, S):
allPaths = []
DFS(root, S, [], allPaths)
return allPaths
def DFS(currentNode, S, currentPath, allPaths):
if currentNode is None: return
currentPath.append(currentNode.val)
# if sum to S, append the path to allPaths
if currentNode.val == S and currentNode.left is None and currentNode.right is None:
allPaths.append(list(currentPath))
else:
# traverse the left sub tree
DFS(currentNode.left, S - currentNode.val, currentPath, allPaths)
# traverse the right sub tree
DFS(currentNode.right, S - currentNode.val, currentPath, allPaths)
# remove the current node to backtrack
del currentPath[-1]
Note: there cannot be more than (N + 1) / 2 leaves in a binary tree, so that total root-to-leaf paths in a binary tree cannot be more than the number of leaves (N + 1) / 2. Therefore, the maximum number of elements in allPaths will be O((N + 1) / 2) = O(N). For a balanced binary tree, the max depth or height is log N, so each path can have log N nodes in it. Therefore, the total size of the allPaths will be O(N log N).
Similar problem: Given a binary tree, return all root-to-leaf paths:
def find_all_paths(root):
allPaths = []
DFS(root, [], allPaths)
return allPaths
def DFS(currentNode, currentPath, allPaths):
if currentNode is None: return
currentPath.append(currentNode.val)
# if reach the leaf
if currentNode.left is None and currentNode.right is None:
allPaths.append(list(currentPath))
else:
# traverse the left sub tree
DFS(currentNode.left, currentPath, allPaths)
# traverse the right sub tree
DFS(currentNode.right, currentPath, allPaths)
# remove the current node to backtrack
del currentPath[-1]
Similar problem: Given a binary tree, find the root-to-leaf pat with the maximum sum.
def find_all_paths(root):
allPaths = {}
DFS(root, 0, [], allPaths)
# there might be multiple paths with the max sum, but can only return one of them
return allPaths[max(allPaths)]
def DFS(currentNode, SUM, currentPath, allPaths):
if currentNode is None: return
currentPath.append(currentNode.val)
SUM += currentNode.val
# if reach the leaf
if currentNode.left is None and currentNode.right is None:
allPaths[SUM] = list(currentPath)
else:
# traverse the left sub tree
DFS(currentNode.left, SUM, currentPath, allPaths)
# traverse the right sub tree
DFS(currentNode.right, SUM, currentPath, allPaths)
# remove the current node to backtrack
SUM -= currentPath[-1]
del currentPath[-1]
3. Sum of Path Numbers
Given a binary tree where each node can only have a digit (0-9) value, each root-to-leaf path will represent a number. Find the total sum of all the numbers represented by all paths.
# Time complexity O(N). Space complexity O(N).
def find_sum_of_path_numbers(root):
return find_root_to_leaf_path_numbers(root, 0)
def find_root_to_leaf_path_numbers(currentNode, pathSum):
if currentNode is None: return 0
pathSum = 10 * pathSum + currentNode.val
if currentNode.left is None and currentNode.right is None:
return pathSum
return find_root_to_leaf_path_numbers(currentNode.left, pathSum) + find_root_to_leaf_path_numbers(currentNode.right, pathSum)
4. Path with Given Sequence
Given a binary tree and a number sequence, find if the sequence if present as a root-to-leaf path in the given tree.
# Time complexity O(N). Space complexity O(N).
def find_path(root, sequence):
if not root:
return len(sequence) == 0
return find_path_recursive(root, sequence, 0)
def find_path_recursive(currentNode, sequence, sequenceIndex):
if currentNode is None: return False
seqlength = len(sequence)
# if exceed the end of the seq, or does not match
if sequenceIndex >= seqlength or currentNode.val != sequence[sequenceIndex]:
return False
# reach the end of the sequence and the leaf of the tree
if currentNode.right is None and currentNode.right is None and sequenceIndex == seqlength -1:
return True
# return True of any side returns True
return find_path_recursive(currentNode.left, sequence, sequenceIndex + 1) or find_path_recursive(currentNode.right, sequence, sequenceIndex + 1)
5. Count Path for a Sum
Given a binary tree and a number S, find all paths in the tree such that the sum of all the node values of each path equals S. Please node that the paths can start or end at any node but all paths must follow direction from parent to child.
# Time complexity O(N^2) in the worst case, O(N log N) if the tree is balanced (the height of a balanced tree is log N).
# Space complexity O(N).
def count_paths(root, S):
return count_paths_recursive(root, S, [])
def count_paths_recursive(currentNode, S, currentPath):
if currentNode is None:
return 0
currentPath.append(currentNode.val)
# A path can start or end at any node
Count, Sum = 0,0
for i in range(len(currentPath) - 1, -1, -1):
Sum += currentPath[i]
if Sum == S: Count += 1
# traverse the left sub tree
Count += count_paths_recursive(currentNode.left, S, currentPath)
# traverse the right sub tree
Count += count_paths_recursive(currentNode.right, S, currentPath)
del currentPath[-1]
return Count
