Inorder Traversal of a Binary Tree using Recursion

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given the root of a binary tree, perform an inorder traversal using recursion and return the list of values in inorder sequence. Inorder traversal visits the left subtree first, then the root node, and finally the right subtree.

Examples❯

Input Tree Inorder Output Description
[1, 2, 3, 4, 5, null, 6]
[4, 2, 5, 1, 3, 6] Standard binary tree with full left subtree and partial right subtree
[1]
[1] Edge case: Tree with only a root node
[] [] Edge case: Empty tree (no nodes present)
[1, 2, null, 3, null, null, null, 4]
[4, 3, 2, 1] Deep left-skewed binary tree
[1, null, 2, null, null, null, 3]
[1, 2, 3] Right-skewed tree: Only right children present

Solution❯

Understanding the Problem

We are given a binary tree and asked to perform an inorder traversal. In inorder traversal, we visit the left subtree first, then the root node, and finally the right subtree. Our goal is to return a list of node values in this exact visiting order.

This problem is fundamental for understanding recursion and tree structures. Let's explore how we can solve it step by step and also ensure our solution gracefully handles all possible cases.

Step-by-Step Solution with Example

Step 1: Understand the Tree Structure

Let’s take an example binary tree:

    1
   /   2   3
 /     4       5

This tree has a left and right subtree. We need to apply the inorder traversal: left → root → right.

Step 2: Define the Recursive Rule

To perform inorder traversal, we write a recursive function that:

  1. Recursively traverses the left subtree.
  2. Adds the current node's value.
  3. Recursively traverses the right subtree.

Step 3: Apply Recursion to the Example

Following our rules on the tree:

  • Start at root 1 → go to left child 2 → go to left child 4 (no left, so add 4)
  • Back to 2 → add 2
  • Back to 1 → add 1
  • Go to right child 3 → go to right child 5 (no left, so add 5)
  • Back to 3 → add 3

The traversal order becomes: [4, 2, 1, 3, 5]

Step 4: Write the Base Case

If the current node is null, we simply return. This avoids any errors while traversing empty branches.

Edge Cases

Case 1: Left Skewed Tree

Tree like: 3 → 2 → 1. All nodes go left. The traversal will be: [1, 2, 3] (deepest left node comes first).

Case 2: Right Skewed Tree

Tree like: 1 → 2 → 3. All nodes go right. The traversal will be: [1, 2, 3].

Case 3: Single Node Tree

Tree with only one node, like 1. The output will be: [1].

Case 4: Empty Tree

If the tree is empty (root is null), we return an empty list: []. This prevents null pointer exceptions and ensures robustness.

Finally

Inorder traversal is a classic recursive problem. By thinking of the traversal as left → root → right and breaking it down into simple steps, we can apply this technique to any tree structure. Handling edge cases like empty trees or skewed trees ensures our solution is both correct and complete.

This understanding also lays the foundation for more complex tree algorithms in the future.

Algorithm Steps❯

  1. Start with the root node of the binary tree.
  2. If the tree is empty, return an empty result.
  3. Recursively perform inorder traversal on the left subtree.
  4. Visit the current node and record its value.
  5. Recursively perform inorder traversal on the right subtree.
  6. Combine the results to produce the final inorder sequence.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

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

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

void inorderTraversal(TreeNode* root, int* arr, int* index) {
    if (root) {
        inorderTraversal(root->left, arr, index);
        arr[(*index)++] = root->val;
        inorderTraversal(root->right, arr, index);
    }
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    int arr[100], index = 0;
    inorderTraversal(root, arr, &index);
    printf("Inorder Traversal: ");
    for (int i = 0; i < index; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...