Tree traversal: pre, in, post

1

I am trying to find a good way to remember how tree traversals work.

At a high level, is it basically:

pre-order = lisp
in-order = infix notation
post-order = forth

?

2

Consider a node N in the tree and let A and B be the two subtrees below N. Then:

  1. pre-order means you consider them in the order N, A, B
  2. in-order means you consider them in the order A, N, B
  3. post-order means you consider them in the order A, B, N

So the pre/in/post word simply determines where the N is in relation to A and B.

7 Likes
3

The way I remember it is where I would put the recursive calls when implementing it in code.

So for pre-order I'll call my callback before recursing, in-order will recurse on left then call the callback then recurse on right, and post-order will do all the recursion before calling the callback.

struct Tree<T> {
    value: T,
    left: Option<Box<Tree<T>>>,
    right: Option<Box<Tree<T>>>,
}

impl<T> Tree<T> {
    fn pre(&self, callback: &dyn Fn(&T)) {
        callback(&self.value);
        if let Some(left) = &self.left { left.pre(callback); 
        if let Some(right) = &self.right { right.pre(callback); }
    }

    fn in_(&self, callback: &dyn Fn(&T)) {
        if let Some(left) = &self.left { left.in_(callback); }
        callback(&self.value);
        if let Some(right) = &self.right { right.in_(callback); }
    }
    
    fn post(&self, callback: &dyn Fn(&T)) {
        if let Some(left) = &self.left { left.post(callback); }
        if let Some(right) = &self.right { right.post(callback); }
        callback(&self.value);
    }
}

(playground)

4 Likes
4

Preorder/inorder/postorder traversal is not particularly related to prefix/infix/postfix notation, except that they use the same Latinate prefixes (no pun intended):

  • pre- meaning "before"
  • in- meaning, well, "in"
  • post- meaning "after"

In prefix notation, an operator is placed (i.e., fixed) before its operands. In preorder graph traversal, a node is visited (i.e., ordered) before its children. Although mathematical notation is often represented with a tree, there is no particularly strong connection between the two concepts.

4 Likes
5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.