Binary Tree Inorder Traversal - Java Solution

1. Introduction

In this post, we'll explore how to perform an inorder traversal of a binary tree. Inorder traversal is a fundamental tree traversal method where we visit the left subtree, the root, and then the right subtree. This type of traversal is commonly used to retrieve elements of a binary tree in their natural order.

Problem

Given the root of a binary tree, the task is to return the inorder traversal of its nodes' values. We need to traverse the tree in a left-root-right order and collect the values of the nodes.

2. Solution Steps

1. Create a list to store the result of the traversal.

2. Use a recursive function to perform the inorder traversal.

3. In the recursive function, traverse the left subtree, add the root's value, and then traverse the right subtree.

4. Return the list containing the traversal result.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTreeInorderTraversal {
    public static void main(String[] args) {
        // Constructing a simple binary tree
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        System.out.println(inorderTraversal(root)); // Test the function
    }

    // Function to perform inorder traversal
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    // Helper function for recursive inorder traversal
    private static void inorder(TreeNode node, List<Integer> res) {
        if (node == null) {
            return;
        }
        inorder(node.left, res); // Traverse left subtree
        res.add(node.val); // Visit root
        inorder(node.right, res); // Traverse right subtree
    }
}

Output:

[1, 3, 2]

Explanation:

1. inorderTraversal: This function initializes a list to store the result and calls the recursive helper function inorder.

2. inorder: A recursive function that performs the inorder traversal. It first calls itself on the left child, then adds the current node's value to the result list, and finally calls itself on the right child.

3. The base case for the recursion is when the node is null, at which point the function returns.

4. As a result, the function accumulates the node values in their inorder sequence in the res list.

5. The main function prints out the list, which represents the inorder traversal of the binary tree.