Binary Tree Traversal — Recursive

Binary Tree is a special tree structure where every node has no more than two children. Example:

A binary tree example

Preorder

Visit the parent node as the first.

1. Visit the parent node
2. Visit the left tree
3. Visit the right tree

Note: it’s visiting the left tree & right tree, not just the left node & right node.

def preorder_traversal(root):
  if not root:
    return
  visit(root)
  preorder_traversal(root.left)
  preorder_traversal(root.right)

If you print out the sequence, the root node must be the first. For the above example, it will be:

1, 2, 4, 5, 3, 6, 7

Inorder

Visit the parent node in the middle.

1. Visit the left tree
2. Visit the parent node
3. Visit the right tree

def inorder_traversal(root):
  if not root:
    return
  inorder_traversal(root.left)
  visit(root)
  inorder_traversal(root.right)

If your print out the sequence, the root node must be somewhere in the middle. For the above example:

4, 2, 5, 1, 6, 3, 7

Postorder

Visit the parent node at the last.

1. Visit the left tree
2. Visit the right tree
3. Visit the parent node

def postorder_traversal(root):
  if not root:
    return
  postorder_traversal(root.left)
  postorder_traversal(root.right)
  visit(root)

If you print out the sequence, the root node must be at the last. For the above example:

4, 5, 2, 6, 7, 3, 1