Binary Tree Inorder Traversal

Loading...LeetCode

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]

Example 2:

Input: root = []
Output: []

Example 3:

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?

You can perform an inorder traversal iteratively using a stack. Here's how you can implement it in JavaScript:

function inorderTraversal(root) {
    const result = [];
    const stack = [];
    let current = root;

    while (current !== null || stack.length > 0) {
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }

        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }

    return result;
}

In this implementation:

• We initialize an empty array result to store the inorder traversal sequence.

• We initialize an empty stack stack to keep track of nodes while traversing the tree.

• We start from the root node and traverse the tree until current is not null or the stack is not empty.

• We push each node encountered while traversing the left subtree into the stack.

• Once we reach a null node, we pop the top node from the stack, add its value to the result array, and move to its right child.

• We repeat this process until we traverse the entire tree.

• Finally, we return the result array containing the inorder traversal sequence.