Binary Tree Inorder 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 inorderTraversal(self, root: TreeNode) -> List[int]:
    res = []
    def inorder(node: TreeNode):
        if not node: return
        inorder(node.left)
        res.append(node.val)
        inorder(node.right)

    inorder(root)
    return res

or even simpler:

def inorderTraversal(self, root: TreeNode) -> List[int]:
    def inorder(root: TreeNode):
        return inorder(root.left) + [root.val] + inorder(root.right) if root else []

    return inorder(root)

Follow Up

Recursive solution is trivial, could you do it iteratively?

Iteration

Complexity

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

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

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

    return res

Morris Traversal

Complexity

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

def inorderTraversal(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:
                # `pre.right` points to root
                pre.right = root
                # traverse left subtree
                root = root.left
            else: # left subtree is done traversing
                res.append(root.val)
                # cut connection
                pre.right = None
                root = root.right
        else:
            res.append(root.val)
            root = root.right
    return res