# Binary Tree Traversal

Visiting every node in a defined order — pre-order, in-order or post-order — each suited to a different task.

**Rests on:** Graph Traversal BFS and DFS, Recursive Thinking

**Leads to:** AlphaGo and MCTS, Balanced Trees and B-Trees, Heaps and Priority Queues, Hierarchical Clustering

*Machine Learning · Data Structures*


## Why learn this

You need to know how to systematically visit every item in a hierarchical list because that is exactly how computers handle nested structures like file folders on your computer or the logic paths in an AI decision-making process. For example, when you ask a smart assistant to find all documents named 'Report' in a folder hierarchy, it must traverse the tree of folders without missing any or visiting one twice. If you understand traversal, you can predict how software navigates complex data, such as checking if a specific file exists in a deep directory structure or evaluating a mathematical formula where operations are nested inside other operations.


## The intuition

Imagine you are organizing a family reunion and need to greet every relative exactly once. You have a large family tree. The 'root' is the oldest ancestor at the top, and everyone else branches out below them. A 'binary tree' means each person has at most two direct descendants (left child and right child). You cannot just jump around; you follow rules. 

Method 1 (Pre-order): You greet the current person first. Then you move to their left branch to greet everyone there, then to their right branch. It is like introducing yourself before meeting your cousins.

Method 2 (In-order): You go deep into the left branch first, greeting everyone all the way down. Then you come back up to greet the current person. Finally, you go to the right branch. If the family members are arranged by age in each branch, this method naturally greets them from youngest to oldest.

Method 3 (Post-order): You visit the left branch first, then the right branch. Only after you have greeted everyone in both branches do you greet the current person. This is useful if you need to count relatives; you must know how many are in each sub-branch before you can announce the total size of that part of the family.

Let’s look at a small example with three people: Ancestor (A), their left child (L), and right child (R). 
- Pre-order visit order: A, then L, then R.
- In-order visit order: L, then A, then R.
- Post-order visit order: L, then R, then A.

The 'subtree' is simply the collection of people under any specific person, including that person. For instance, the subtree rooted at A includes A, L, and R. The subtree rooted at L includes only L.


## An analogy

Think of a Christmas tree with ornaments. To take it down, you have three choices. Pre-order is like writing 'Tree' on a card before you start, then handling the left side, then the right. In-order is like sorting the ornaments by size: you finish the left side (smaller ornaments), then place the current trunk section's ornament (medium), then handle the right side (larger). Post-order is like packing for storage: you wrap up all the left branches, then all the right branches, and finally pack the main trunk. The order determines whether you process the structure before its parts, after its parts, or in a sorted sequence between them. This analogy holds because each branch must be fully dealt with according to the rule before moving on, just as you cannot wrap a box until its contents are packed.


## Definition

Binary tree traversal is a method for visiting every node (individual point) in a hierarchical structure exactly once by following strict rules about when to process the current node relative to its left and right branches. A subtree is the sub-section of the structure rooted at any given node, containing that node and all its descendants.


## How it connects

This concept sits beside Depth-First Search, which is a general technique for exploring nodes by going as deep as possible along each branch before backtracking, and Recursion, which is a programming pattern where a function calls itself to handle smaller versions of the same problem. You use these together to navigate data structures like file systems or decision trees.


## The mathematics

Traversal is about order, not arithmetic. The branch of mathematics here is discrete mathematics, specifically combinatorics and graph theory, because we are dealing with a structure of nodes and edges. The core operation is not a calculation but a systematic enumeration—a way of listing all elements exactly once.

To understand the three main types of traversal, imagine you are visiting every room in a house that is built like a tree. You start at the entrance (the root) and must visit every room before you leave. The rule for *when* you write down the name of the room depends on which type of traversal you are doing.

**Pre-order Traversal**
In pre-order, you follow this strict sequence for every node (room):
1. Visit the current node first. Write its name down immediately.
2. Then, go to the left child (the left branch) and do the same thing: visit it, write its name, then check its left and right children.
3. Only after you have finished visiting every node in the entire left subtree do you move to the right child (the right branch) and repeat the process.

Think of it as "Parent before Children." You meet the parent first, then go explore their left side completely, then go explore their right side completely.

**In-order Traversal**
In in-order, the sequence is different:
1. First, go to the left child and visit every node in that left subtree (following the same rules recursively).
2. Once the left side is fully visited, come back and visit the current node. Write its name down now.
3. Finally, go to the right child and visit every node in that right subtree.

Think of it as "Left before Parent." You clear out everything on the left first, then you handle the current node, then you handle everything on the right. This order is especially useful for Binary Search Trees because it lists the values from smallest to largest.

**Post-order Traversal**
In post-order, the sequence is:
1. First, go to the left child and visit every node in that left subtree.
2. Then, go to the right child and visit every node in that right subtree.
3. Only after both children are fully visited do you come back and visit the current node. Write its name down last.

Think of it as "Children before Parent." You must finish dealing with all the descendants before you deal with the ancestor itself. This is useful for tasks like deleting a tree, where you want to remove the leaves before removing the branches that hold them.


## A worked example

Let us walk through a specific example step by step. We will use a small binary tree.

**The Tree Structure**
- The root node (the top) has the value **10**.
- The left child of 10 has the value **5**.
- The right child of 10 has the value **15**.
- The left child of 5 has the value **2**.
- The right child of 5 has the value **7**.

Visually, it looks like this:
      10
     /  \
    5    15
   / \
  2   7

We will determine the order in which we visit these numbers for each traversal type. We start at the root (10).

**Step 1: Pre-order Traversal (Parent, Left, Right)**
Rule: Visit current node -> Go Left -> Go Right.

1. Start at **10**. Write down **10**.
2. Move to the left child of 10, which is **5**.
   - At node 5, visit it first. Write down **5**.
   - Move to the left child of 5, which is **2**.
     - At node 2, visit it first. Write down **2**.
     - Node 2 has no children. We are done with this branch.
   - Move to the right child of 5, which is **7**.
     - At node 7, visit it first. Write down **7**.
     - Node 7 has no children. We are done with this branch.
   - We have finished visiting all nodes in the subtree rooted at 5.
3. Move to the right child of 10, which is **15**.
   - At node 15, visit it first. Write down **15**.
   - Node 15 has no children. We are done.

Resulting Sequence: **10, 5, 2, 7, 15**

**Step 2: In-order Traversal (Left, Parent, Right)**
Rule: Go Left -> Visit current node -> Go Right.

1. Start at root **10**. We must go left first.
   - Move to left child **5**. We must go left first from here too.
     - Move to left child **2**.
       - Node 2 has no left child. So, visit node 2. Write down **2**.
       - Node 2 has no right child. Return to parent (5).
     - Now that the left side of 5 is done, visit node 5. Write down **5**.
     - Now go to the right child of 5, which is **7**.
       - Node 7 has no left child. Visit node 7. Write down **7**.
       - Node 7 has no right child. Return to parent (10).
   - Now that the entire left subtree of 10 is done, visit node 10. Write down **10**.
2. Now go to the right child of 10, which is **15**.
   - Node 15 has no left child. Visit node 15. Write down **15**.
   - Node 15 has no right child. Done.

Resulting Sequence: **2, 5, 7, 10, 15**
Note that because this is a Binary Search Tree (where left children are smaller and right children are larger), the in-order traversal gives us the numbers in sorted ascending order.

**Step 3: Post-order Traversal (Left, Right, Parent)**
Rule: Go Left -> Go Right -> Visit current node.

1. Start at root **10**. We must go left first.
   - Move to left child **5**. We must go left first from here too.
     - Move to left child **2**.
       - Node 2 has no left child.
       - Node 2 has no right child.
       - Now visit node 2. Write down **2**.
       - Return to parent (5).
     - Now go to the right child of 5, which is **7**.
       - Node 7 has no left child.
       - Node 7 has no right child.
       - Now visit node 7. Write down **7**.
       - Return to parent (5).
     - Now that both children of 5 are visited, visit node 5. Write down **5**.
     - Return to parent (10).
   - Now go to the right child of 10, which is **15**.
     - Node 15 has no left child.
     - Node 15 has no right child.
     - Now visit node 15. Write down **15**.
     - Return to parent (10).
   - Now that both children of 10 are visited, visit node 10. Write down **10**.

Resulting Sequence: **2, 7, 5, 15, 10**


## From scratch, in Python

```python
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def pre_order(node):
    if node is None:
        return
    print(node.value)
    pre_order(node.left)
    pre_order(node.right)

def in_order(node):
    if node is None:
        return
    in_order(node.left)
    print(node.value)
    in_order(node.right)

def post_order(node):
    if node is None:
        return
    post_order(node.left)
    post_order(node.right)
    print(node.value)

# Build the tree from the example
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)

print('Pre-order:')
pre_order(root)
print('In-order:')
in_order(root)
print('Post-order:')
post_order(root)
```


## What the code does

First, we define a Node class. Each node has a value, a left child, and a right child. The left and right are initially None. Then we define three recursive functions. Each function takes a node. If the node is None (base case), we just return. Otherwise, we follow the order: for pre-order, print the value, then recursively call on left, then on right. For in-order, go left first, then print, then right. For post-order, go left, then right, then print. Finally, we build the tree with the same structure as the numerical example and call each function.


## Common misconceptions

**Traversal is only for trees** — Traversal is a concept that only applies to tree structures and has no use elsewhere.

The same idea of visiting nodes in order applies to graphs, filesystems, and even expression evaluation. Depth-first search on a graph is a generalisation of tree traversal. In fact: Traversal is a fundamental pattern for visiting all elements of a connected structure, and trees are just a restricted case of graphs.

**In-order always gives sorted output** — In-order traversal always returns elements in sorted order.

In-order traversal gives sorted order only when the tree is a binary search tree (BST), where the left subtree contains smaller values and the right subtree larger values. If the tree is not a BST, in-order gives no meaningful sorted order. In fact: In-order traversal of a binary search tree yields sorted output, but for arbitrary binary trees, the order is just a traversal order with no sorting guarantee.

**Pre-order is the most natural** — Pre-order is the default and most intuitive traversal order, so it should be used for everything.

Each order has its own use case. For example, post-order is necessary when children must be processed before parents (e.g., deleting a tree, or computing the size of a subtree). Pre-order is not universally the best. In fact: The choice of traversal order depends on the task: pre-order for copying a tree, in-order for sorted output in a BST, post-order for deleting or evaluating after children.

**Traversal requires a stack** — All traversals require an explicit stack or queue to keep track of nodes.

Recursive traversal uses the call stack implicitly, which is a stack, but you can also do iterative traversal with an explicit stack. However, there are also Morris traversal algorithms that use no stack at all by temporarily modifying the tree. In fact: Traversal can be implemented recursively (using the call stack) or iteratively with an explicit stack; Morris traversal achieves it without any stack, by temporarily rewiring pointers.

**Traversal is O(n^2)** — Traversal is inefficient and has quadratic time complexity.

In a balanced tree, each node is visited exactly once, so the time complexity is O(n), where n is the number of nodes. Even in an unbalanced tree, it's still O(n) because each node is visited once. In fact: Binary tree traversal visits each node once, so the time complexity is O(n), which is linear in the number of nodes.


## In short

Binary tree traversal is the systematic way to visit every node exactly once. The three main orders—pre-order, in-order, and post-order—differ only in where the node visit happens relative to its subtrees. In-order of a BST gives sorted output; post-order is used when children must be processed before parents; and each can be implemented recursively or iteratively. Traversal is O(n) and is a building block for many tree-based algorithms in AI.


## Where this is used

In large language models, tree traversal appears in parsing the token sequence into a parse tree during preprocessing. For example, when a model reads code, an abstract syntax tree (AST) is traversed in-order to generate the token sequence. In small models that run on devices, a decision tree model is traversed in pre-order to make a prediction, which is efficient because it only follows one path. In retrieval-augmented generation, documents are often stored in a B-tree index, and traversal is needed to extract all documents in sorted order. Agentic systems that plan and call tools use tree-structured planning: the system explores different possible actions by traversing a search tree, using post-order to evaluate a plan after its sub-actions have been explored. In everyday applied machine learning, gradient boosting (like XGBoost) builds many decision trees; for each tree, predictions are made by traversing the tree in pre-order, and the trees themselves are built using recursive splitting that is post-order. A developer writing a decision tree classifier in scikit-learn doesn't implement traversal manually—the library does it internally. But if you were to write a custom decision tree, you'd write recursive functions like the ones above. When traversal is done incorrectly, the most common bug is missing the base case or mixing up the order, which leads to wrong predictions or infinite recursion.


---

Read this on the web: https://basavapurushottam.com/learn-ai/binary-tree-traversal
