Inorder Traversal of Binary Tree Explained with Examples

Inorder​‍​‌‍​‍‌​‍​‌‍​‍‌ tree traversal is a method that allows one to go through all the nodes of a binary tree in a particular sequence. The idea is pretty simple: first, access the left child, then the current node, and finally, the right child. The tree is traversed in this manner for each node, going down from the root.

        1
     /    \
    2     3
   / \     /
  4   5  6

1. Begin at the root (node 1) and then go to its left child, which is node 2.
2. From node 2, go further left - node 4
3. Node 4 has no children, so we visit it
4. Go back to node 2 and visit it
5. Then move to node 2’s right child -  node 5, and visit it
6. Now return to the root node (1) and visit it
7. Move to node 1’s right child - node 
8. From node 3, go to its left child -  node 6, and visit it
9. Finally, go back and visit node 3

Final Output:

4 → 2 → 5 → 1 → 6 → 3

This Left -> Node -> Right order is what defines inorder traversal of binary tree. It ensures that nodes are visited in a way that naturally reflects the sorted order in binary search trees.

Implementing inorder traversal of binary tree follows a clear, modular workflow. Regardless of the programming language, the logic remains the same.

Core Steps

1. Define the TreeNode structure
   Each node stores:
   
   • A data value
   • A reference to the left child
   • A reference to the right child
2. Construct the binary tree
   Nodes are instantiated and linked to form the tree structure.
3. Integrate the inorder traversal logic
   The traversal follows the Left → Node → Right order using:
   
   • A recursive depth-first approach, or
   • An iterative approach using a stack‍
4. Execute traversal on the constructed tree
   The traversal function is called with the root node, producing the inorder sequence.

Example: Complete Python Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def inorder_traversal(root):
    result = []

    def helper(node):
        if node is None:  # base case
            return
        helper(node.left)
        result.append(node.val)
        helper(node.right)

    helper(root)
    return result


# Construct the tree
root = TreeNode(1, TreeNode(2), TreeNode(3))

print(inorder_traversal(root))  # Output: [2, 1, 3]

Best Practices

• Base​‍​‌‍​‍‌​‍​‌‍​‍‌ cases should always be defined so as to avoid null reference errors. 
• Instead of using global variables, it is better to use a helper function with a local result array/vector. 
• In case of very deep or skewed trees, it is advisable to use an iterative or Morris traversal method to be able to handle the situation without stack overflow.
• It is helpful to separate tree construction from traversal tree for better understanding and reusability.

Bottom Line

By using these patterns and steps, you have the ability to go through, build, and describe binary trees by inorder traversal in any of the widely used programming languages with a high degree of certainty. Such a modular manner of working is an assurance of your code being correct, flexible, and ​‍​‌‍​‍‌​‍​‌‍​‍‌clear.

Inorder tree traversal implementation is language-agnostic, once you understand the structure + traversal flow, you can code it confidently in Python, Java, C++, or JavaScript.

Inorder traversal of binary tree can be implemented using different techniques depending on performance needs and tree size. The two most commonly used methods are the recursive approach, which relies on the call stack, and the iterative approach, which uses an explicit stack to control traversal flow.

1. Implementation of Recursive Approach for Inorder Traversal

The​‍​‌‍​‍‌​‍​‌‍​‍‌ recursive approach is the most natural and commonly taught way of doing an inorder traversal of binary tree. It uses the inherent hierarchical nature of trees and the capability of function recursion to recursively go through each node in the right ​‍​‌‍​‍‌​‍​‌‍​‍‌order.

Core Logic

In recursive inorder traversal, the logic is simple:
For any given node, you want to:

1. Recursively traverse its left subtree.
2. Process the current node (for example, print its value or add it to a result list).
3. Recursively traverse its right subtree.

This left → node → right pattern is followed for every node, starting from the root. Recursion makes sure that each subtree is processed in the same way, whether it’s small or large, so the traversal stays consistent throughout the tree.

Implementation Steps

The implementation typically involves a helper function that receives a node as input and follows these steps:

1. Base Case: If the node is None, return immediately.
   This stops the recursion when a leaf node’s child is reached.
2. Recursive Call on Left Subtree:
   Call the helper function on the node’s left child.
3. Process Current Node:
   Perform the desired operation with the current node’s value (such as adding it to a result list).
4. Recursive Call on Right Subtree:
   Call the helper function on the node’s right child.

Pseudocode Example

Here’s a language-agnostic pseudocode for recursive inorder tree traversal:

function inorder(node):
if node is None: 
        return

    INORDER(node.left)
    process(node.value)
    INORDER(node.right)

Python Example

def inorder_traversal(root):
    def helper(node, result):
        if node is None:
            return
        helper(node.left, result)
        result.append(node.value)
        helper(node.right, result)

    result = []
    helper(root, result)
    return result

C Example

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* newNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;

    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

int main() {
    struct TreeNode* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);

    inorderTraversal(root);   // Output: 2 1 3
    return 0;
}

C++ Example

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void inorderTraversal(TreeNode* root) {
    if (root == nullptr)
        return;

    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    inorderTraversal(root);   // Output: 2 1 3
    return 0;
}

Java Example

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class InorderTraversal {

    static void inorderTraversal(TreeNode root) {
        if (root == null)
            return;

        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        inorderTraversal(root);   // Output: 2 1 3
    }
}

How Recursion Works

When you call the function on the left child, the current node’s context is saved on the call stack. Once the left subtree is fully processed, control returns to the current node, which is then processed, and finally, the function moves to the right subtree. This stack-based management of function calls ensures the correct left-node-right order.

Common Patterns

• Base Case First: Always check if the current node is None before proceeding.
• Result List: Use a result list that is either passed as an argument or defined within the helper function’s scope to collect node values in order.
• No Global Variables: Avoid using global or static variables for results, as this can lead to bugs if the function is called multiple times.

Time and Space Complexity

• Time Complexity: O(n), here, n is the number of nodes. The algorithm goes through each node once.
• Space Complexity: O(h), where h stands for the height of the tree. This is attributable to the recursion call stack. In the worst scenario (a skewed tree), h may be equal to ​‍​‌‍​‍‌​‍​‌‍​‍‌n. 

Why Use Recursion?

Recursion closely mirrors the tree’s hierarchical structure, making the code simple and easy to understand. It is the standard approach for inorder traversal and provides a clear, direct mapping to the conceptual definition of the traversal order.

2. Iterative Approach for Inorder Traversal of Binary Tree

The iterative approach to inorder traversal uses an explicit stack to simulate the call stack used in recursion. This method is especially useful for avoiding recursion depth limits in large or skewed trees and provides better control over the traversal process.

Core Logic

The main idea is to traverse as far left as possible, pushing nodes onto the stack as you go. Once you reach a node with no left child, you process the node (add its value to the result list), then move to its right child. This process continues until all nodes have been visited and the stack is empty.

Implementation Steps

1. Initialize an empty stack and set the current node to the root.
2. Iterate while the current node is not null or the stack is not empty:
   
   • Go as far left as possible, pushing each node onto the stack.
   • When a node with no left child is reached, pop the top node from the stack.
   • Add the node's value to the result list.
   • Move to the node's right child and repeat the process.
3. End the loop when both the stack is empty and the current node is null.

Pseudocode

INORDER_ITERATIVE(root):
    stack = []
    current = root
    result = []

    while current is not null OR stack is not empty:
        while current is not null:
            stack.push(current)
            current = current.left

        current = stack.pop()
        result.append(current.value)
        current = current.right

    return result

Python Example

def inorder_iterative(root):
    stack = []
    current = root
    result = []

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result

C Example

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

/* Stack structure for TreeNode pointers */
struct Stack {
    struct TreeNode** data;
    int top;
    int capacity;
};

struct Stack* createStack(int capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->data = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    return stack;
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void push(struct Stack* stack, struct TreeNode* node) {
    stack->data[++stack->top] = node;
}

struct TreeNode* pop(struct Stack* stack) {
    return stack->data[stack->top--];
}

/* Iterative inorder traversal */
void inorderIterative(struct TreeNode* root) {
    struct Stack* stack = createStack(100);
    struct TreeNode* current = root;

    while (current != NULL || !isEmpty(stack)) {
        while (current != NULL) {
            push(stack, current);
            current = current->left;
        }

        current = pop(stack);
        printf("%d ", current->val);
        current = current->right;
    }
}

C++ Example

vector<int> inorderIterative(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    TreeNode* current = root;

    while (current != nullptr || !st.empty()) {
        while (current != nullptr) {
            st.push(current);
            current = current->left;
        }

        current = st.top();
        st.pop();
        result.push_back(current->val);
        current = current->right;
    }

    return result;
}

Java Example

List<Integer> inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> result = new ArrayList<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }

    return result;
}

Key Concepts and Terms

• Stack: Used to keep track of nodes whose left children are being explored.
• Push: Before going to the left, put the current node into the stack.
• Pop: Retrieve a node from the stack when there are no more left children.
• Infinite Loop/Break the Loop: The loop continues until both the stack is empty and there is no current node.
• Left Child/Right Child: Always traverse left children first, process the node, then move to right children.
• Result List: Stores the final inorder traversal sequence.

Key Properties of the Iterative Inorder Traversal Approach

The iterative approach for inorder traversal of binary tree has several important properties that distinguish it from other methods:

• Order Preservation:
  Similar to the recursive method, the iterative version also goes through the nodes in a strict Left → Node → Right manner, thereby resulting in a proper inorder traversal.
• Stack Usage:
  It uses an explicit stack to keep track of nodes, effectively simulating the system call stack used in recursion.
• Handles Large/Deep Trees:
  Avoiding recursion prevents stack overflow issues that can occur with very deep or skewed trees.
• Space Complexity:
  The additional space used is O(h), where h is the tree's height. This is due to the stack, which has the capacity to hold every node along a single path from the root to a leaf.
• No Recursion Required:
  The approach works entirely with loops and a stack, making it suitable in environments where recursion is limited or discouraged.
• Consistent Output:
  When used on a Binary Search Tree (BST), the iterative approach, like the recursive one, returns node values in sorted (ascending) order.
• Deterministic Traversal:
  All nodes are visited only once, and the traversing is straightforward and can be easily checked for ​‍​‌‍​‍‌​‍​‌‍​‍‌correctness.

Summary

The iterative approach to inorder traversal provides a reliable and efficient way to traverse binary trees without recursion. By explicitly managing the stack, you avoid recursion depth issues and maintain full control over the traversal process, ensuring every node is visited in the correct left-node-right order.

Comparison with Recursive Approach

• Recursive Approach: Recursion depth may restrict the code's conciseness since it makes use of the system call stack to remember nodes.
• Iterative Approach: Uses an explicit stack, making it more robust for deep or unbalanced trees and giving more control over traversal.

Beyond recursive and iterative methods, inorder traversal also includes advanced techniques that optimize space usage and enable tree reconstruction. These approaches are very helpful in memory-limited devices, deep trees, and interview-level problem-solving scenarios.

1. Morris Inorder Traversal

The Morris inorder traversal of binary tree is an efficient way to traverse a binary tree without using recursion or a stack. It temporarily alters the tree structure to establish threaded connections between nodes.

Code Example:

def morris_inorder(root):
    current = root
    while current:
        if current.left is None:
            print(current.data, end=' ')
            current = current.right
        else:
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right
            if pre.right is None:
                pre.right = current
                current = current.left
            else:
                pre.right = None
                print(current.data, end=' ')
                current = current.right

Code Explanation:

The Morris inorder traversal binary tree traversal works by visiting each node and temporarily modifying the tree structure. When a node has a left child, the algorithm finds the rightmost node in its left subtree (predecessor), creates a temporary link to the current node, and moves to the left child. 

Once the left subtree is processed, it removes the temporary link, prints the current node, and moves to the right child. This process avoids the use of additional space for recursion or a stack.

Output:

For a binary tree like:

      1
     / \
    2  3
   /  \
  4   5

The output will be:

4 2 5 1 3

Time and Space Complexity:

• Time Complexity: O(n), here, n is the number of nodes in the tree.
• Space Complexity: O(1) since the algorithm uses constant space regardless of the tree size.

2. Binary Tree Construction from Inorder and Preorder

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_value = preorder[0]
    root = TreeNode(root_value)
    root_index_in_inorder = inorder.index(root_value)
    
    root.left = buildTree(preorder[1:root_index_in_inorder+1], inorder[:root_index_in_inorder])
    root.right = buildTree(preorder[root_index_in_inorder+1:], inorder[root_index_in_inorder+1:])
    
    return root

Code Explanation:

This binary tree construction from inorder and preorder takes two lists preorder and inorder, as input and constructs a binary tree. It begins by selecting the first element from the preorder list as the root node, then locates this root within the inorder list to divide it into left and right subtrees.

It then recursively builds the left and right subtrees using the corresponding elements from the inorder preorder lists. When there are no more items to process, the recursion ends.

Output:

The inorder preorder function will return the root of the reconstructed binary tree.

preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

Time and Space Complexity:

• Time Complexity: The time complexity is O(n) because each node is visited once.
• Space Complexity: The space complexity is O(n) due to the recursion stack and the space required to store the tree.

3. Binary Tree Construction from Inorder and Postorder Traversal

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def buildTree(postorder, inorder):
    if not inorder or not postorder:
        return None
    root_value = postorder[-1]
    root = TreeNode(root_value)
    root_index_in_inorder = inorder.index(root_value)
    
    root.left = buildTree(postorder[:root_index_in_inorder], inorder[:root_index_in_inorder])
    root.right = buildTree(postorder[root_index_in_inorder:-1], inorder[root_index_in_inorder+1:])
    
    return root

Code Explanation:

This binary tree construction from inorder and postorder takes two lists postorder and inorder as input and constructs a binary tree. The process begins by selecting the last item from the postorder list as the root node. Next, this root is located within the inorder list to divide the tree into left and right subtrees. 

Recursively, it builds the left and right subtrees by passing the appropriate sections of the postorder and inorder lists. The recursion stops when no elements are left to process.

Output:

The function will return the root of the reconstructed binary tree.

postorder = [9, 15, 7, 20, 3]
inorder = [9, 3, 15, 20, 7]

Time and Space Complexity:

• Time Complexity: The time complexity is O(n) as each node is visited only once.
• Space Complexity: The space complexity is O(n), which is attributable to the recursion stack and the space taken up by the tree. 

Quick Recap:

• Morris Inorder Traversal performs traversal without recursion or a stack, using temporary links in the tree.
• It achieves O(1) extra space complexity, making it ideal for memory-constrained systems.
• The tree structure is restored after traversal, so no permanent changes are made.
• Binary tree reconstruction is possible by combining inorder traversal with preorder or postorder traversal.
• These techniques are commonly tested in technical interviews and are useful for large or complex trees.

To determine if a binary tree is a valid Binary Search Tree (BST), inorder binary tree traversal is useful. When we perform an inorder traversal of binary tree on a BST, the elements are returned in sorted order. If the result is not sorted, then the tree is not a valid BST.

2. Expression Tree Evaluation

Inorder traversal is used for evaluating expression trees. An expression tree represents mathematical expressions where each leaf node is an operand, and each internal node is an operator. When we traverse this tree in inorder, it outputs the expression in infix notation (e.g., A + B * C).

3. Tree Serialization and Deserialization

A binary tree can be serialized (converted into an easily stored format) and deserialized (rebuilt from that format) using inorder traversal when combined with other traversal techniques like preorder or postorder. This is useful for storing and retrieving tree structures.

4. Finding the Kth Smallest Element in a BST

Identifying the Kth smallest element in a Binary Search Tree is made efficient by inorder traversal, which processes the nodes in a sorted sequence. We can easily get the Kth least element by only counting the nodes while traversing the tree in reverse order.

Implementing​‍​‌‍​‍‌​‍​‌‍​‍‌ inorder traversal might look simple, but it is riddled with mistakes that could potentially cause wrong outputs or runtime errors. Here’s a brief summary of the common pitfalls and the corresponding prevention measures:

1. Incorrect Traversal Order (Not Left-Node-Right)

One of the most common errors is a misconception that the current node should be processed before the left subtree is visited, or after the right subtree has been visited. In this case, one unintentionally switches the traversal type (for example, to preorder or postorder), thus an incorrect sequence is ​‍​‌‍​‍‌​‍​‌‍​‍‌obtained.

• Correct order:
  
  1. Traverse left subtree
  2. Visit current node
  3. Traverse right subtree
• Pitfall example:
  Processing​‍​‌‍​‍‌​‍​‌‍​‍‌ the node before the left subtree (root-left-right) is a preorder traversal, not an inorder one.

2. Missing or Improper Base Case in Recursion

If you do not check whether the current node is None before accessing its children, you will get runtime errors (for example, AttributeError in Python).

• Correct approach:
  It is a good practice to check whether the node is None at the very beginning of the function and return right away in this case.

3. Inefficient List Concatenation

There are several implementations that return concatenated lists from the recursive calls, thus they consume more memory and their performance is ​‍​‌‍​‍‌​‍​‌‍​‍‌slower.

• Pitfall example:
  Returning inorder(left) + [root.val] + inorder(right) creates new lists at each step.
• Better approach:
  Instead of accumulating the result within each recursive call differentially, consider a shared result list, which can either be passed as an argument or held within the function's scope.

4. Using Global or Persistent Variables for Results

Storing traversal results in a global variable is prone to errors if the function is invoked multiple times in the same program run.

• Best practice:
  The result list should be local to the function or the class instance.

5. Not Handling Edge Cases

Not thinking of empty trees, trees with only one node, or extremely unbalanced trees may result in errors and incomplete traversals.

• Checklist:
  
  • Test with an empty tree (root is None)
  • Test with a single-node tree
  • Test with left-skewed and right-skewed trees

6. Stack/Recursion Depth Issues in Large Trees

If​‍​‌‍​‍‌​‍​‌‍​‍‌ you have extremely deep or heavily unbalanced trees, recursion may reach the maximum stack depth in certain programming languages. You might want to use iterative or Morris traversal methods instead in such situations.

Summary Checklist for Correct Inorder Traversal:

• Never forget checking whether the node is None before the recursion.
• Strictly adhere to the left → node → right ​‍​‌‍​‍‌​‍​‌‍​‍‌order.
• Use a local result list, not a global one.
• Avoid list concatenations in recursive returns.
• Test on various tree shapes, including edge cases.

Inorder traversal can be done in a dependable and performant manner by enclosing these potential errors in one's ​‍​‌‍​‍‌​‍​‌‍​‍‌thoughts. 

Inorder traversal of binary tree is among the most important concepts in the data structures and algorithms field. Its significance can be seen in various operations like searching in binary search trees (BST), tree validation, expression evaluation, and tree reconstruction.

Learning both the recursive and iterative methods, along with advanced techniques such as Morris inorder traversal, provides a solid foundation for technical interviews and practical applications. When combined with other traversals like binary tree construction from inorder and postorder, inorder traversal becomes vital for working with and navigating complex tree data structures.

Points to Remember

1. Inorder traversal follows the Left → Node → Right order, and in a Binary Search Tree (BST), this naturally returns values in sorted (ascending) order.
2. Recursive and iterative approaches produce the same output, but the iterative method uses an explicit stack and is safer for deep or skewed trees.
3. Each​‍​‌‍​‍‌​‍​‌‍​‍‌ node will be visited only one time. Thus, inorder traversal has a time complexity of O(n) in any case.
4. Morris inorder traversal gets rid of the additional space usage and thus has a space complexity of O(1) since it changes and later restores the tree links temporarily.
5. Inorder traversal alone cannot reconstruct a binary tree; it must be combined with preorder or postorder traversal to rebuild the original structure.

1. How is inorder traversal different from preorder and postorder?

Inorder traverses the tree in the order of left, root, and right nodes. Preorder traversal is performed in the sequence root-left-right, and postorder is left-right-root. They all have different use cases.

2. What is inorder traversal used for?

It's helpful for getting sorted values from a BST, checking the tree structure, or solving problems like finding the kth smallest element.

3. What is Morris inorder traversal and how does it work?

It is a method of traversing a tree without the need for recursion or the use of additional memory. Though it works by temporarily changing the tree, it always restores it.

4. Can you build a binary tree using just inorder traversal?

Not by itself. To reconstruct the whole tree you need either inorder and preorder or postorder recordings.

5. Why is inorder traversal important in BSTs?

Because it returns values in sorted order, it's great for checking or using the BST's sorted nature.

6. What is the difference between preorder, inorder, and postorder traversal?

Preorder, inorder, and postorder traversal are three depth-first ways to visit nodes in a binary tree, and they differ in the order in which the root node is processed.

• Preorder traversal follows Root → Left → Right and is commonly used for tree copying and prefix expression generation.
• Inorder traversal follows Left → Root → Right and returns sorted output in Binary Search Trees (BSTs).
• Postorder traversal follows Left → Right → Root and is useful for deleting trees and evaluating postfix expressions.

Each of the preorder inorder postorder traversals serves a different purpose depending on the problem being solved.