Tree Traversal

Notes on tree traversal in Python.

This is a set of notes that covers three types of tree traversal: pre-order, in-order, and post-order.

• Pre-order: root -> left -> right
• In-order: left -> root -> right
• Post-order: left -> right -> root

These are all depth-first searches.

Pre-order

Process the root, then the left subtree, then the right subtree.

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

Iterative

def preorder(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            print(node.val)
            stack.append(node.right)
            stack.append(node.left)

In-order

Implementation

Iterative

Both of these work the same in that as long as you can go left, you go left. Once you can’t go left anymore, you pop off the stack, process the node, and then go right (where you’ll try to go left again).

def inorder(root):
    stack = []
    while stack or root:
        if root:
            stack.append(root)
            root = root.left
        else:
            root = stack.pop()
            print(root.val)
            root = root.right

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

When to use in-order

In-order is useful for binary search trees, because it will return the values in sorted order. This is because the left subtree is always less than the root, and the right subtree is always greater than the root.

For example, if you have a BTS and want to return the kth smallest element, you can do an in-order traversal and return the kth element you pop off the stack.

Post-order

This is the same as pre-order, except you process the root after the left and right subtrees.

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val)

When to use post-order

Post-order is useful for deleting nodes in a tree. If you delete the children before the parent, you can’t access the children anymore.

Examples

Construct Binary Tree from Preorder and Inorder Traversal

This is a problem where you’re given the pre-order and in-order traversals of a tree as lists, and you need to construct the tree.

For example, given this tree:

the input is preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7].

The key is to realize that the first element in the pre-order list is the root of the tree. You can then find that element in the in-order list, and everything to the left of it is the left subtree, and everything to the right of it is the right subtree.

This problem is also hard, because you need to combine recursion with iteraively moving through the preorder list.

First Step

At the first step preorder_index = 0 whose value is 3, which maps to the first element in the in-order list. This is the root of the tree.

root = TreeNode(preorder[preorder_index])

# this can be optimized by using a hashmap
inorder_index = inorder.index(preorder[preorder_index])

# increment the preorder index
preorder_index += 1

The inorder_index then tells you which slice of the in-order list is the left and right subtrees.

root.left = helper(left, inorder_index - 1)
root.right = helper(inorder_index + 1, right)

The process will then continue recursively until the left and right pointers are equal, which means you’ve reached the end of the tree so you can return None.

Full LeetCode solution:

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def helper(left, right):
            nonlocal preorder_index
            if left > right:
                return None

            root = TreeNode(preorder[preorder_index])
            preorder_index += 1

            inorder_index = inorder_map[root.val]

            root.left = helper(left, inorder_index - 1)
            root.right = helper(inorder_index + 1, right)

            return root

        preorder_index = 0
        inorder_map = {val: idx for idx, val in enumerate(inorder)}
        return helper(0, len(preorder) - 1)