# Tree traversal: pre, in, post

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

?

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

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)

3 Likes

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

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.