Binary Tree Inorder Traversal

EASY

Description

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Approaches

Checkout 3 different approaches to solve Binary Tree Inorder Traversal. Click on different approaches to view the approach and algorithm in detail.

Recursive Inorder Traversal

This is the most straightforward and intuitive approach. The structure of the recursive algorithm directly mirrors the definition of an inorder traversal (Left, Root, Right). We create a helper function that is called recursively on the left child, then processes the current node, and finally is called on the right child.

Algorithm

The core idea of inorder traversal is to visit nodes in the order: Left Subtree, Root, Right Subtree. A recursive function naturally models this process.

Define a helper function, let's say inorderHelper(TreeNode node, List<Integer> result).
The base case for the recursion is when the node is null. In this case, we simply return.
If the node is not null: a. Make a recursive call on the left child: inorderHelper(node.left, result). b. After the left subtree has been fully traversed, visit the current node by adding its value to the result list: result.add(node.val). c. Finally, make a recursive call on the right child: inorderHelper(node.right, result).
The main function initializes an empty list and calls the helper function with the root of the tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }

    private void inorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // 1. Traverse the left subtree
        inorderHelper(node.left, result);
        // 2. Visit the root node
        result.add(node.val);
        // 3. Traverse the right subtree
        inorderHelper(node.right, result);
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the tree, because we visit each node exactly once.Space Complexity: O(H), where H is the height of the tree. In the worst case of a skewed tree, this becomes O(N), where N is the number of nodes. In the best case of a balanced tree, it's O(log N). This space is used by the recursion call stack.

Pros and Cons

Pros:

The code is simple, clean, and easy to understand as it directly follows the definition of inorder traversal.
It requires minimal code to implement.

Cons:

For very deep or skewed trees, this can lead to a StackOverflowError because the depth of the recursion call stack can exceed its limit.
The space used by the call stack is implicit and not directly controlled by the programmer.

Code Solutions

Checking out 4 solutions in different languages for Binary Tree Inorder Traversal. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Binary Tree Inorder Traversal

Algorithms:

Depth-First Search

Data Structures:

StackTreeBinary Tree

Companies:

Adobe |Amazon |Apple |Bloomberg |