https://leetcode.com/problems/binary-tree-inorder-traversal/ Easy 0 attempts
LeetCode ↗

https://leetcode.com/problems/binary-tree-inorder-traversal/

Easy TreeBinary TreeDFS LeetCode

Given the root of a binary tree, return the inorder traversal of its nodes' values. Inorder traversal visits nodes in the order: left subtree, root, then right subtree. This produces sorted order for BSTs. Implement the solution iteratively using a stack for better space understanding.

Example 1:

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

Example 2:

Input: root = []
Output: []
Sample Input
—
Sample Output
—
Constraints
  • 0 <= Number of nodes <= 100
  • -100 <= Node.val <= 100
Test Cases
Case 1
Args: [[1,null,2,3]] Expected: [1,3,2]
Case 2
Args: [[]] Expected: []
Case 3
Args: [[1]] Expected: [1]
Topics
TreeBinary TreeDFS

Approach: Iterative with Stack

Use a stack to simulate the recursive inorder traversal. Push all left children onto the stack, then pop, record the value, and move to the right child. Repeat until both stack and current pointer are exhausted.

function binaryTreeInorderTraversal(root) {
  const result = [], stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) { stack.push(curr); curr = curr.left; }
    curr = stack.pop();
    result.push(curr.val);
    curr = curr.right;
  }
  return result;
}

Time Complexity: O(n)

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript