January 9th, 2020

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

Raymond Chen
Raymond Chen

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.

Category
Old New Thing
Topics
Code

Author

Raymond Chen

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.

5 comments

Discussion is closed. Login to edit/delete existing comments.

  • 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).

  • Henke37

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

    • Frédéric B.

      Well it needs the tree to be doubly linked (parents have links to children, and children have links to parents too), which isn’t the case of the “naïve” tree example.

      If you follow a more “state machine” approach, you need a little more state, such as having both the current node and the previous one (to know whether you are coming from the parent, or a child, and which one).

    • Raymond ChenMicrosoft employee Author

      That surprised me too!

Read next