Binary Tree: In-order Traversal

Representation

We represent the node as:

Node =>
    Value
    Node Left
    Node Right

In-order Traversal

The in-order traversal is a kind of depth-first traversal. We perform the following steps:

• Recursively traverse the node’s left subtree in in-order
• Access the node
• Recursively traverse the node’s right subtree in in-order

After traversing the left and the right subtrees of the root node, we consider the traversal complete.

In-order Traversal

Example

We will do the in-order traversal on the following binary tree:

Binary Tree for In-order Traversal

The nodes in yellow are not yet visited, and the subtrees with dashed edges are also not visited yet. The in-order traversal visits the nodes D, G, B, H, E, A, C, and F.

In-order Traversal

Let’s take a look at each visit separately. We start with the root node, i.e., node A. By…