Tree DFS

There are three ways to traverse (depends on where you want to put your rootNode)

[!important]
For iteratively, when we visit, we pop the note out

1. Preorder

^33568e

rootNode comes before its children, hence the name

Recursive

def preOrderTraversal(rootNode: TreeNode) -> None:
    if not rootNode:
        return None
    visit(rootNode)

    preOrderTraversal(rootNode.left)
    preOrderTraversal(rootNode.right)

Iterative
We're using stack

def preOrderTraversalIterative(rootNode: TreeNode) -> None:
    if not rootNode:
        return None

    stack = deque([rootNode])
    while stack:
        currNode = stack.popleft()
        visit(currNode)
        # Node add the right first before left for next iteration to pop the left first
        if (currNode.right):
            stack.appendleft(currNode.right)
        if (currNode.left):
            stack.appendleft(currNode.left)

2. Inorder

^2f6900

rootNode inbetween the childrens. So left, root, right

Recursive

def inorderOrderTraversal(rootNode: TreeNode) -> None:
    if not rootNode:
        return None

    inorderOrderTraversal(rootNode.left)
    visit(rootNode)
    inorderOrderTraversal(rootNode.right)

Iterative

def inorderOrderTraversalIterative(rootNode: TreeNode) -> None:
    if not rootNode:
        return None

    curr = rootNode
    stack = deque() # NOTE the stack is empty here

    while stack or curr:
        while curr is not None:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        visit(curr)
        curr = curr.right

^825f14

3. PostOrder

rootNode comes after the children. So left, right, root

Recursive

def postorderOrderTraversal(rootNode: TreeNode) -> None:
    if not rootNode:
        return None

    postorderOrderTraversal(rootNode.left)
    postorderOrderTraversal(rootNode.right)
    visit(rootNode)

Iterative
To pop the parent, we need to check for 2 conditions:

• If there is no right child
• If the right child is already visited
  • To check if the right child is already visited, we need to store the last visited right child in a variable so that next turn we can cross check if we have already visited that children

def postorderOrderTraversalIterative(rootNode: TreeNode) -> None:
    if not rootNode:
        return None

    currNode = rootNode
    stack = deque() # NOTE the stack is empty here
    lastVisitedNode = None

    while stack or currNode:
        while currNode is not None:
            stack.append(currNode)
            currNode = currNode.left

        currNode = stack[-1]

        # If no right child or the right child is explored previously
        if (currNode is None or lastVisitedNode == currNode.right):
            self.visit(stack.pop())
            lastVisitedNode = currNode
            currNode = None
        else:
	        # Else go to the right
	        currNode = currNode.right

Time Complexity

• $O(n)$
  • $n$: number of node in the tree