DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All interview questions

Interview preparation

Binary Tree Inorder Traversal

EasyTreesStacks and QueuesRecursion
MicrosoftAmazon Community-reported practice tags — not verified company questions.

1Problem statement

Given the root of a binary tree, return the inorder traversal (left, node, right) of its values. Follow-up: can you do it iteratively?

2Examples

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

3Constraints

  • 0 ≤ number of nodes ≤ 100
  • −100 ≤ Node.val ≤ 100

4Approaches

Approach 1

Brute Force: Recursion

inorder(left), visit node, inorder(right).

Time O(n)Space O(h) call stack

Approach 2

Better: Iterative with a stack

Push all left children, pop and visit, then move to the right child.

Time O(n)Space O(h)

Approach 3

Optimal (space): Morris traversal

Temporarily thread the tree to walk it without a stack.

Time O(n)Space O(1)

5Code (optimal approach)

Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function inorderTraversal(root) {
  const result = [];
  const stack = [];
  let node = root;
  while (node !== null || stack.length > 0) {
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    result.push(node.val);
    node = node.right;
  }
  return result;
}

function buildTree(values) {
  if (values.length === 0 || values[0] === null) return null;
  const root = new TreeNode(values[0]);
  const queue = [root];
  let i = 1;
  while (queue.length > 0 && i < values.length) {
    const node = queue.shift();
    if (i < values.length && values[i] !== null) queue.push((node.left = new TreeNode(values[i])));
    i++;
    if (i < values.length && values[i] !== null) queue.push((node.right = new TreeNode(values[i])));
    i++;
  }
  return root;
}

console.log(inorderTraversal(buildTree([1, null, 2, 3])));
console.log(inorderTraversal(buildTree([4, 2, 6, 1, 3, 5, 7])));

6Complexity

Time

O(n)

Space

O(h)

7Visual walkthrough

Related visualization (Binary Tree Inorder Traversal) — shows the core data-structure operations this solution relies on:

Binary Tree Inorder Traversalinteractive Open full visualizer
4261357
result =[]
Current callOn the call stackBeing visitedVisited

Recursively visits the left subtree, then the node itself, then the right subtree (Left → Root → Right). On a Binary Search Tree this produces the values in sorted order.

1 / 67

8Related questions

Number of Islands

On this page

  1. 01Problem statement
  2. 02Examples
  3. 03Constraints
  4. 04Approaches
  5. 05Code (4 languages)
  6. 06Complexity
  7. 07Visual walkthrough
  8. 08Related questions