DevBlogs
January 9th, 2020

# Tree-walking algorithms: Incrementally performing an inorder walk of a binary tree

We continue our exploration of algorithms for walking incrementally through a tree by perform an inorder walk through a binary tree. (Note that inorder traversal is meaningful only for binary trees.)

Recall that our goal is to follow the red arrows through the tree, as if we are walking along the outside of the tree with our left hand touching it.

 â†™ï¸Ž A â†–ï¸Ž â†™ï¸Ž â•±â†—ï¸Ž â†’ï¸Ž â†˜ï¸Žâ•² â†–ï¸Ž â†™ï¸Ž B â†‘ï¸Ž â†“ï¸ŽÂ C Â â†‘ â†™ï¸Ž â•± â†· â•²â†–ï¸Ž â†™ï¸Žâ•± â†’ â¤´ï¸Ž â†“ï¸ŽÂ D â†‘â†“ E Â â†–ï¸ŽÂ â†“ï¸Ž F Â â†‘ â¤· â†’ â¤´ï¸Žâ¤·ï¸Ž â†’ â¤´ï¸Žâ¤·ï¸Ž â†’ â¤´ï¸Ž

Since we are doing an inorder traversal, the fact that we stopped on a node means that we have finished enumerating the left child and need to start enumerating the right child, if there is one.

If there is no right child, then we have finished enumerating the entire subtree, and we need to walk up the tree looking for another subtree to the right. This step is a little tricky: When we move to the parent, we need to check whether we moved up from the left child or from the right child. If we moved up from the left child, then the right child is the subtree to the right. If we moved up from the right child, then there is no subtree to the right at this level, and we need to go up another level.

```class InorderWalker
{
private TreeCursor cursor;

public InorderWalker(TreeNode node)
{
cursor = new TreeCursor(node);
GoDeepLeft();
}

public bool MoveNext()
{
if (cursor.TryMoveToRightChild()) {
GoDeepLeft();
return true;
}

TreeNode start;
do {
start = cursor.Current;
if (!cursor.TryMoveToParent()) {
return false;
}
} while (start != cursor.Current.LeftChild);
return true;
}

public TreeNode Current => cursor.Current;

private void GoDeepLeft()
{
while (cursor.TryMoveToLeftChild()) { }
}
}
```

I think that’s enough incremental tree traversal algorithms for now.

Topics
Code

## Author

Raymond has been involved in the evolution of Windows for more than 30 years. In 2003, he began a Web site known as The Old New Thing which has grown in popularity far beyond his wildest imagination, a development which still gives him the heebie-jeebies. The Web site spawned a book, coincidentally also titled The Old New Thing (Addison Wesley 2007). He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information.

Popular
Oldest
• Motti Lanzkron

Did you put the wrong diagram by mistake? The diagram in use isn’t of a binary tree (B, C and D are all children of A).

• Oops, fixed.

• Henke37

I’m stunned by the fact that none of these required keeping more state than the single cursor.