Home > Topics

🌳➡️ Tree Traversal

From Wikipedia: Tree traversal

• In-order, pre-order, and post-order are 3 common forms of depth-first tree traversal.
• While traversing a non-linear data structure (such as a tree) we have choices for which node to visit next.
  • Therefore, we must store references to nodes we’re not visiting yet for later retrieval.
  • This is commonly done explicitly in a stack or queue, or implicitly in the call stack of a recursive function.
• Depth-first search is easily implemented with a stack (explicitly or implicitly via the call stack).
• The sequence of nodes visited in a tree traversal is called a trace.
• None of these 3 traversal orders produces a trace that uniquely defines a tree.
  🤔 Interesting. This fact doesn’t seem obvious to me.

Given a tree with distinct elements, either pre-order or post-order paired with in-order is sufficient to describe the tree uniquely. However, pre-order with post-order leaves some ambiguity in the tree structure.

🤔 Okay, so pre-order and post-order traversals have some sort of structural similarity that isn’t shared with an in-order traversal.

Depth-First Traversal Orders

In depth-first traversals, the children sub-trees are searched recursively.

Mnemonics

• Pre-order visits the parent node before (hence pre) the children.
• Post-order visits the parent node after (hence post) the children.
• In-order visits the parent node in-between the children.
  • also: in-order traversal would return the elements of a binary search tree in order.

Pre-order

flowchart  
1 --> 2  
1 --> 3  

Post-order

flowchart  
3 --> 1  
3 --> 2  

In-order

flowchart  
2 --> 1  
2 --> 3  

Reverse pre-order

flowchart  
3 --> 2  
3 --> 1  

Reverse post-order

flowchart  
1 --> 3  
1 --> 2  

Reverse in-order

flowchart  
2 --> 3  
2 --> 1  

Level-order

AKA Breadth-first search (BFS)

🦋 Bluesky

🌳➡️ Tree Traversal

AI Q: 🌳 Which traversal method makes the most logical sense to you?

🌳 Data Structures | 🔍 Search Algorithms | 🪜 Recursive Functions | 📊 Graph Theory
https://bagrounds.org/topics/tree-traversal

— Bryan Grounds (@bagrounds.bsky.social) 2026-05-03T01:46:20.000Z

🐘 Mastodon

Post by @bagrounds@mastodon.social

View on Mastodon