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

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.

5 comments

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

  • Henke37 0

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

    • Raymond ChenMicrosoft employee 0

      That surprised me too!

    • Frédéric B. 0

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

  • Motti Lanzkron 0

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

    • Raymond ChenMicrosoft employee 0

      Oops, fixed.

Feedback usabilla icon