Binary Tree Traversal in DSA (Inorder, Preorder, Postorder)

Introduction

Binary Tree Traversal is one of the most important topics in Data Structures and Algorithms (DSA). It is frequently asked in interviews because it checks your understanding of trees, recursion, and problem-solving logic.

In simple words, tree traversal means visiting every node of a binary tree in a specific order.

In this article, we will understand the three most common types of binary tree traversals:

Inorder Traversal
Preorder Traversal
Postorder Traversal

All concepts are explained in easy language, with examples and clean code.

What is a Binary Tree?

A Binary Tree is a tree data structure in which:

Each node has at most two children
These children are called left child and right child

Each node contains:

A value (data)
A reference to the left child
A reference to the right child

What is Tree Traversal?

Tree traversal is the process of visiting each node of the tree exactly once.

Because a tree is not linear like an array or list, we need specific rules to decide which node to visit first, second, and so on.

Traversal helps in:

Printing all nodes
Searching values
Evaluating expressions

Types of Binary Tree Traversal

There are three main types of depth-first traversals:

Inorder Traversal
Preorder Traversal
Postorder Traversal

Each traversal follows a different visiting order.

Inorder Traversal (Left → Root → Right)

In Inorder Traversal, we visit nodes in the following order:

Visit the left subtree
Visit the root node
Visit the right subtree

Why Inorder Traversal is Important

Inorder traversal of a Binary Search Tree gives values in sorted order
Commonly used in tree-based problems

Example

For a tree:

    1
   / \
  2   3

Inorder traversal output:

2 1 3

Preorder Traversal (Root → Left → Right)

In Preorder Traversal, we visit nodes in the following order:

Visit the root node
Visit the left subtree
Visit the right subtree

Why Preorder Traversal is Important

Used to copy a tree
Useful in expression tree evaluation

Example

For the same tree:

    1
   / \
  2   3

Preorder traversal output:

1 2 3

Postorder Traversal (Left → Right → Root)

In Postorder Traversal, we visit nodes in the following order:

Visit the left subtree
Visit the right subtree
Visit the root node

Why Postorder Traversal is Important

Used to delete a tree safely
Helpful in evaluating postfix expressions

Example

For the same tree:

    1
   / \
  2   3

Postorder traversal output:

2 3 1

Recursive Approach for Tree Traversal

Binary tree traversals are most commonly implemented using recursion because trees naturally follow a recursive structure.

Each traversal uses the same logic pattern but with a different visiting order.

Code Implementation

Node Structure (Common)

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) {
        data = val;
        left = right = NULL;
    }
};

Inorder Traversal Code

void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

Preorder Traversal Code

void preorder(Node* root) {
    if (root == NULL) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

Postorder Traversal Code

void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

Java Code Example (Inorder)

void inorder(Node root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.data + " ");
    inorder(root.right);
}

Python Code Example (Preorder)

def preorder(root):
    if root is None:
        return
    print(root.data, end=" ")
    preorder(root.left)
    preorder(root.right)

Time and Space Complexity

Time Complexity: O(n) for all traversals
Space Complexity: O(h), where h is the height of the tree (due to recursion stack)

Edge Cases to Consider

Empty tree
Tree with only one node
Highly skewed tree

Always handle these cases carefully.

Common Interview Questions on Tree Traversal

Difference between inorder, preorder, and postorder
Iterative tree traversal
Level order traversal (BFS)
Traversal without recursion

Summary

Binary Tree Traversal is a fundamental concept in DSA that helps you understand how tree structures are processed. Inorder, Preorder, and Postorder traversals differ only in the order of visiting nodes, but all are equally important for interviews. By understanding their logic and practicing recursive implementations, you build a strong foundation for solving advanced tree-based problems in coding interviews.