NeetCode 19번 알고리즘 : Depth-First Search

3 types of Depth-First Search

- Inorder

- Preorder

- Postorder

 

Inorder Traversal 

Recursive

def inorder(root):
    if not root:
        return    
    inorder(root.left)
    print(root.val)
    inorder(root.right)

 

Iterative

def inorderTraversal(self, root):
        curr = root
        stack = []
        ans = []

        while (curr or stack) :
            while curr :
                stack.append(curr)
                curr= curr.left
            curr = stack.pop()
            ans.append(curr.val)
            curr= curr.right
        return ans

Preorder Traversal 

def preorder(root):
    if not root:
        return    
    print(root.val)
    preorder(root.left)
    preorder(root.right)

 

Postorder Traversal 

def preorder(root):
    if not root:
        return    
    preorder(root.left)
    preorder(root.right)
    print(root.val)

 

Complexity

Time Complexity : O(n)

Space Complexity: O(n)

   - Iterative : Explicit Stack

   - Recursive : Call Stack 

 

Sorting using Binary Tree

Time Complexity = Time to search the tree + Time to build the tree = O(n + nlogn) = O(nlogn)