Inorder Traversal

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Visit left subtree, then root, then right subtree. For iterative: use stack to simulate call stack.

Algorithm

1Recursive: inorder(left), visit root, inorder(right).
2Iterative: push all left nodes to stack. Pop, add to result, then push all left nodes of right subtree.

Common Pitfalls

•Morris traversal achieves O(1) space by temporarily modifying tree links.

Inorder Traversal.java

Java

// Approach: Recursive or iterative in-order (left-root-right) traversal of binary tree.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class Solution {
    // Function to return a list containing the inorder traversal of the tree.
    ArrayList<Integer> inOrder(Node root) {
        ArrayList<Integer> arr = new ArrayList<>();
        helper(root, arr);
        return arr;
    }

    void helper(Node root, ArrayList<Integer> arr) {
        if (root == null)
            return;

        helper(root.left, arr);
        arr.add(root.data);
        helper(root.right, arr);
    }
}

Was this solution helpful?