DFS for Trees

There are three ways of traversing a tree by using a DFS approach, and these can be done both iteratively and recursively.

1. Pre-order traversal.
2. In-order traversal.
3. Post-order traversal.

Pre-order traversal

The traversal order is:

1. Node.
2. Left.
3. Right.

The iterative and recursive solutions can be tested in LeetCode.

from typing import List, Optional


class TreeNode:
    def __init__(self, val,
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


from typing import List, Optional


class Solution:
    def preorderTraversal(self, root: Optional[TreeNode] = None) -> List[int]:
        def dfs(node: Optional[TreeNode] = None) -> None:
            if not node:
                return

            nonlocal res
            res.append(node.val)

            for child in [node.left, node.right]:
                dfs(child)

        res = []
        dfs(root)

        return res

from typing import List, Optional


class TreeNode:
    def __init__(self, val,
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


from typing import List, Optional


class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)

            for child in [node.right, node.left]:
                if child:
                    stack.append(child)

        return res

In-order traversal

The traversal order is:

1. Left.
2. Node.
3. Right.

The iterative and recursive solutions can be tested in LeetCode.

from typing import List, Optional


class TreeNode:
    def __init__(self, val,
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


from typing import List, Optional


class Solution:
    def inorderTraversal(self, root: Optional[TreeNode] = None) -> List[int]:
        def dfs(node: Optional[TreeNode] = None) -> None:
            if not node:
                return

            dfs(node.left)

            nonlocal res
            res.append(node.val)

            dfs(node.right)

        res = []
        dfs(root)

        return res

from typing import List, Optional


class TreeNode:
    def __init__(self, val,
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


from typing import List, Optional


class Solution:
    def inorderTraversal(self, root: Optional[TreeNode] = None) -> List[int]:
        if not root:
            return []

        res = []
        stack = [root]

        while stack:
            node = stack.pop()
            while node:
                stack.append(node)
                node = node.left

            if stack:
                node = stack.pop()
                res.append(node.val)
                stack.append(node.right)

        return res

Post-order traversal

The traversal order is:

1. Left.
2. Right.
3. Node.

The iterative and recursive solutions can be tested in LeetCode.

from typing import List, Optional


class TreeNode:
    def __init__(self, val,
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


from typing import List, Optional


class Solution:
    def postorderTraversal(self, root: Optional[TreeNode] = None) -> List[int]:
        def dfs(node: Optional[TreeNode] = None) -> None:
            if not node:
                return

            dfs(node.left)
            dfs(node.right)

            nonlocal res
            res.append(node.val)

        res = []
        dfs(root)

        return res

from typing import List, Optional


class TreeNode:
    def __init__(self, val,
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


from typing import List, Optional


class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        res = []
        # Each element of stack is a tuple: (node, visited_flag)
        stack = [(root, False)]

        while stack:
            node, visited = stack.pop()
            if visited:
                res.append(node.val)
            else:
                stack.append((node, True))

                for child in [node.right, node.left]:
                    if child:
                        stack.append((child, False))

        return res