Data Structures and Algorithms (DSA)  

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:

  1. Inorder Traversal

  2. Preorder Traversal

  3. Postorder Traversal

Each traversal follows a different visiting order.

Inorder Traversal (Left → Root → Right)

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

  1. Visit the left subtree

  2. Visit the root node

  3. 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:

  1. Visit the root node

  2. Visit the left subtree

  3. 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:

  1. Visit the left subtree

  2. Visit the right subtree

  3. 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.

Membership not found