5 months, 1 week

# Coding Patterns: Depth First Search

Depth-first search is an algorithm for traversing or searching tree or graph data structures. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph. This also means that the space complexity of the algorithm will be O(H), where H is the maximum height of the tree.

Depth First Traversals:

(a) Inorder (Left, Root, Right)

(b) Preorder (Root, Left, Right)

(c) Postorder (Left, Right, Root) :

LeetCode 112 - Path Sum [easy]

Given the `root` of a binary tree and an integer `targetSum`, return `true` if the tree has a root-to-leaf path such that adding up all the values along the path equals `targetSum`.

leaf is a node with no children.

To recursively traverse a binary tree in a DFS fashion, we can start from the `root` and at every step, make two recursive calls one for the `root.left` and one for the `root.right` child by subtracting the value of the current node from the given number: `sum - root.val`.

1. Solution:

class Solution:
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False

sum  -=  root.val
if not root.left and not root.right:
return sum == 0
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

2. Solution

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

Time ComplexityO(N) where `N` is the total number of nodes in the tree.

Space ComplexityO(N), this space will be used to store the recursion stack.

When the problem asks the traversal of a tree, you should think about DFS pattern and use it in combination with a recursive approach.

LeetCode 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Solution:

class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(node):
if not node:
return 0
r = dfs(node.right)
l = dfs(node.left)
if l == -1 or r == -1 or abs(l - r)>1:
return -1
return max(l,r) + 1
return dfs(root) != -1

LeetCode 257. Binary Tree Paths

Given the `root` of a binary tree, return all root-to-leaf paths in any order.

leaf is a node with no children.

Solution:

class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
ans = []

def dfs(root: Optional[TreeNode], path: List[str]) -> None:
if not root:
return
if not root.left and not root.right:
ans.append(''.join(path) + str(root.val))
return

path.append(str(root.val) + '->')
dfs(root.left, path)
dfs(root.right, path)
path.pop()

dfs(root, [])
return ans

• Time: O(n)
• Space: O(h)

See all(3)

Tags

Topics
Related