Definition:In-Order Traversal of Labeled Tree

Definition

Let $T$ be a binary labeled tree.

In-order traversal of $T$ is an algorithm designed to obtain a string representation of $T$.

The steps are as follows:

Variant 1

$\mathtt{Inorder} (T):$

• $n \gets t$, where $t$ is the root node of $T$.
• If $n$ is a leaf node, output the label of $n$, and stop.
• Let $T_1$ and $T_2$ be the left and right subtrees of $T$.
• If $n$ has only one child, skip this step. Output $\mathtt{Inorder} (T_1)$.
• Output the label of $n$.
• Output $\mathtt{Inorder} (T_2)$.
• Stop.

Variant 2

$\mathtt{Inorder} (T):$

• $n \gets t$, where $t$ is the root node of $T$.
• If $n$ is a leaf node, output the label of $n$, and stop.
• Let $T_1$ and $T_2$ be the left and right subtrees of $T$.
• Output a left bracket $($.
• If $n$ has only one child, skip this step. Output $\mathtt{Inorder} (T_1)$.
• Output the label of $n$.
• Output $\mathtt{Inorder} (T_2)$.
• Output a right bracket $)$.
• Stop.

Also see

• Pre-Order Traversal of Labeled Tree