What is a traversal

Specific way of visiting nodes in a tree.

Types of traversals

BFS

Breadth-first search.

DFS

Depth-first search has three types:

• Pre-order (rLR)
  • root-left-right
• In-order (LrR)
  • left-root-right
• Post-order (LRr)
  • left-right-root

Think about where the root is positioned relative to left and right.

Time complexity: O(n) where n is the number of nodes in the tree.

Space complexity: O(h); where h is the height of the tree (max number of function calls in the stack).

Recursive traversal

In-order Traversal (left-root-right)

Steps

• move from root, to the right-most leaf node.
• start visiting nodes starting from the left-most subtree
• traversal makes its way back to the root
• traverse to the right subtree

Javascript:

function inOrderTraversal(node) {
  if (node !== null) {
    inOrderTraversal(node.left);
    visitNode(node);
    inOrderTraversal(node.right);
  }
}

Python:

In-order Traversal (left-root-right)

def in_order_traversal(root):
    if root is None:
        return

    # Traverse the left subtree
    in_order_traversal(root.left)

    # Visit the root node (Print the value)
    print(root.value, end=" ")

    # Traverse the right subtree
    in_order_traversal(root.right)

Pre-order Traversal (root-left-right)

def pre_order_traversal(root):
    if root is None:
        return

    # Visit the root node (Print the value)
    print(root.value, end=" ")

    # Traverse the left subtree
    pre_order_traversal(root.left)

    # Traverse the right subtree
    pre_order_traversal(root.right)

Post-order Traversal (left-right-root)

def post_order_traversal(root):
    if root is None:
        return

    # Traverse the left subtree
    post_order_traversal(root.left)

    # Traverse the right subtree
    post_order_traversal(root.right)

    # Visit the root node (Print the value)
    print(root.value, end=" ")