Binary Tree Inorder Traversal

Easy
1859.

Binary Tree Inorder Traversal

Binary Tree Inorder Traversal is an easy coding problem on depth-first search, trees and stack, asked in Amazon, Google and Microsoft interviews.

Given the root of a binary tree, return the values of its nodes in inorder: for every node, first everything in its left subtree, then the node itself, then everything in its right subtree.

Example 1

Input
root = [1,null,2,3]
Output
[1,3,2]
Explanation
Node 1 has no left child, so it comes first; then its right subtree, where 3 (the left child of 2) precedes 2.

Example 2

Input
root = [4,2,6,1,3,5,7]
Output
[1,2,3,4,5,6,7]
Explanation
This tree is a binary search tree, and an inorder walk of a BST always lists its values in sorted order.

Example 3

Input
root = []
Output
[]

Constraints

  • The number of nodes in the tree is in the range [0, 100]
  • -100 <= Node.val <= 100

Follow-up: The recursive walk is short — can you do it iteratively with an explicit stack?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Inorder Traversal — Problem & Solution

Binary Tree Inorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Binary Tree Inorder Traversal is an easy coding problem on depth-first search, trees and stack, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given the root of a binary tree, return the values of its nodes in inorder: for every node, first everything in its left subtree, then the node itself, then everything in its right subtree.

Example 1

Input: root = [1,null,2,3]
Output: [1,3,2]
Explanation: Node 1 has no left child, so it comes first; then its right subtree, where 3 (the left child of 2) precedes 2.

Example 2

Input: root = [4,2,6,1,3,5,7]
Output: [1,2,3,4,5,6,7]
Explanation: This tree is a binary search tree, and an inorder walk of a BST always lists its values in sorted order.

Example 3

Input: root = []
Output: []

Constraints

  • The number of nodes in the tree is in the range [0, 100]
  • -100 <= Node.val <= 100

Follow-up: The recursive walk is short — can you do it iteratively with an explicit stack?

Hints for Binary Tree Inorder Traversal

  1. Hint 1

    Inorder is a rule you apply at every node: left subtree, the node, right subtree.

  2. Hint 2

    A recursive helper that appends to one shared list follows that rule directly; the base case is an empty subtree.

  3. Hint 3

    Iteratively: push nodes while walking left; when you fall off, pop a node, record it, and continue from its right child.

How to solve Binary Tree Inorder Traversal

Inorder is defined recursively — left subtree, node, right subtree — so a depth-first walk that records each node between its two recursive calls produces the order exactly. An explicit stack does the same work without recursion.

Approach

  1. Start with an empty result list and an empty stack; set cur = root.
  2. While cur is not null, push it and move to cur.left.
  3. When cur is null and the stack is not empty, pop a node, append its value, and set cur to its right child.
  4. Stop when both cur is null and the stack is empty.

Why it works

A node is popped only after its entire left chain — and so its entire left subtree — has been pushed and popped, and its right subtree is started only after it has been recorded. That is precisely the inorder rule applied at every node.

Complexity

  • Time — O(n) — every node is pushed and popped once
  • Space — O(h) for the stack (or the recursion), where h is the tree's height — O(n) for a chain

Pitfalls

  • An empty tree returns an empty list, not an error.
  • Recording the node before descending left gives preorder, not inorder.
  • A tree that is a long left chain makes the stack as tall as the tree.

Reference solution

Python

from typing import List, Optional

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    out = []
    stack = []
    cur = root
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.val)
        cur = cur.right
    return out

Java

public static int[] inorderTraversal(TreeNode root) {
    List<Integer> out = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        out.add(cur.val);
        cur = cur.right;
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> out;
    vector<TreeNode*> stack;
    TreeNode* cur = root;
    while (cur || !stack.empty()) {
        while (cur) {
            stack.push_back(cur);
            cur = cur->left;
        }
        cur = stack.back();
        stack.pop_back();
        out.push_back(cur->val);
        cur = cur->right;
    }
    return out;
}

JavaScript

var inorderTraversal = function(root) {
    var out = [], stack = [], cur = root;
    while (cur !== null || stack.length > 0) {
        while (cur !== null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        out.push(cur.val);
        cur = cur.right;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals