Binary Tree Preorder Traversal

Definition for a Binary Tree Node

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Solution

Let $n$ be the number of nodes in the tree.

Recursion

Complexity

time: $O(n)$
space: $O(n)$

def preorderTraversal(self, root: TreeNode) -> List[int]:
    res = []
    def preorder(node: TreeNode):
        if not node: return
        res.append(node.val)
        preorder(node.left)
        preorder(node.right)

    preorder(root)
    return res

Follow Up

Recursive solution is trivial, could you do it iteratively?

Iteration

Complexity

time: $O(n)$
space: $O(n)$

def preorderTraversal(self, root: TreeNode) -> List[int]:
    res = []
    stack = [root]

    while stack:
        curr = stack.pop()
        if curr:
            res.append(curr.val)
            stack.append(curr.right)
            stack.append(curr.left)

    return res

Morris Traversal

Complexity

time: $O(n)$
space: $O(1)$

def preorderTraversal(self, root: TreeNode) -> List[int]:
    res = []
    pre = None

    while root:
        if root.left:
            pre = root.left
            while pre.right and pre.right != root:
                pre = pre.right

            if not pre.right:
                res.append(root.val)
                # `pre.right` points to root
                pre.right = root
                # traverse left subtree
                root = root.left
            else: # left subtree is done traversing
                # cut connection
                pre.right = None
                root = root.right
        else:
            res.append(root.val)
            root = root.right
    return res