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

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

Easy TreeBinary TreeDFS LeetCode

You're given the root of a binary tree. Walk it in inorder order — left subtree first, then the current node, then the right subtree — and return the node values you collect, in that order. Applying this traversal to a binary search tree naturally yields the values in ascending order. Rather than relying on recursion, write an iterative version that uses an explicit stack, which makes the space usage easier to reason about.

Input Format
Implement binaryTreeInorderTraversal(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
root = []
Output
[]

Example 3

Input
root = [1]
Output
[1]
Constraints
  • 0 <= Number of nodes <= 100
  • -100 <= Node.val <= 100
Test Cases (3)
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.

javascript
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