Inorder Traversal of a Binary Tree using Recursion

Problem and examples

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.

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

Explore Inorder Traversal of a Binary Tree - Recursion

Load an example or enter your own input. Use the player controls to follow each change.

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:

Recursively traverses the left subtree.
Adds the current node's value.
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.

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

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

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

void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (root) {
        inorderTraversal(root->left, result);
        result.push_back(root->val);
        inorderTraversal(root->right, result);
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    vector<int> result;
    inorderTraversal(root, result);
    cout << "Inorder Traversal: ";
    for (int val : result)
        cout << val << " ";
    cout << endl;
    return 0;
}

Python implementation

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

def inorderTraversal(root):
    if not root:
        return []
    return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(inorderTraversal(root))

Java implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class RecursiveInorderTraversal {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    private void inorder(TreeNode root, List<Integer> result) {
        if (root != null) {
            inorder(root.left, result);
            result.add(root.val);
            inorder(root.right, result);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        RecursiveInorderTraversal sol = new RecursiveInorderTraversal();
        System.out.println(sol.inorderTraversal(root));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorderTraversal(root) {
    if (!root) return [];
    return inorderTraversal(root.left).concat(root.val, inorderTraversal(root.right));
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log(inorderTraversal(root));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func inorderTraversal(root *TreeNode, result *[]int) {
    if root != nil {
        inorderTraversal(root.Left, result)
        *result = append(*result, root.Val)
        inorderTraversal(root.Right, result)
    }
}

func main() {
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, nil, nil}}
    var result []int
    inorderTraversal(root, &result)
    fmt.Println("Inorder Traversal:", result)
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn inorder_traversal(root: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder_traversal(&node.left, result);
        result.push(node.val);
        inorder_traversal(&node.right, result);
    }
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
    }));
    let mut result = vec![];
    inorder_traversal(&root, &mut result);
    println!("Inorder Traversal: {:?}", result);
}

Kotlin implementation

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun inorderTraversal(root: TreeNode?, result: MutableList<Int>) {
    if (root != null) {
        inorderTraversal(root.left, result)
        result.add(root.value)
        inorderTraversal(root.right, result)
    }
}

fun main() {
    val root = TreeNode(1).apply {
        left = TreeNode(2).apply {
            left = TreeNode(4)
            right = TreeNode(5)
        }
        right = TreeNode(3)
    }
    val result = mutableListOf<Int>()
    inorderTraversal(root, result)
    println("Inorder Traversal: $result")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

func inorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
}

let root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print("Inorder Traversal: \(inorderTraversal(root))")

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function inorderTraversal(root: TreeNode | null): number[] {
    if (!root) return [];
    return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)];
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log("Inorder Traversal:", inorderTraversal(root));