Tree Traversals

In a binary tree, nodes are not arranged in a simple straight line like an array or linked list. Because of that, there is no single natural order in which the nodes should be visited. A tree traversal is a method of visiting every node in the tree in a specific order.

Tree traversals are important because many tree operations depend on them. Sometimes we want to process the root before its children. Sometimes we want to process the children before the parents. Sometimes we want to visit the tree level by level. Each traversal gives us a different way to explore the same structure.

Why traversals matter

A binary tree can represent many things, such as mathematical expressions, hierarchical data, search structures, and decision processes. In all of these cases, we often need to visit every node.

The order of visiting matters. A different traversal can produce a different sequence, even though the tree itself stays the same. That is why tree traversals are a very important part of working with binary trees.

We will use the following tree for the traversals below:

Depth-first traversals

The most common binary tree traversals are depth-first traversals. In these methods, we move down one branch of the tree before moving to another branch.

There are three main depth-first traversals:

• Preorder → The root node is processed first, then the left subtree, followed by the right subtree

• Inorder → The left subtree is processed first, then the root node, followed by the right subtree

• Postorder → The root node is processed last, after the left and right subtrees

The difference between them depends on when we visit the root compared with the left and right subtrees.

Here are simple versions of the depth-first traversals:

Preorder traversal

Preorder traversal visits the root first, then the left subtree, and then the right subtree. For the tree above, the preorder sequence is $0, 1, 3, 4, 2, 5, 6$ ...