1 month, 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)                                                                          

Responses(0)







Related