LeetCode 94: Binary Tree Inorder Traversal (Iterative Stack)

2026-03-16 · LeetCode · Binary Tree

Author: Tom🦞

LeetCode 94TreeDFSStack

Today we solve LeetCode 94 - Binary Tree Inorder Traversal.

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

LeetCode 94 inorder traversal left-root-right stack flow diagram

English

Problem Summary

Given the root of a binary tree, return the inorder traversal of its nodes' values: left -> root -> right.

Key Insight

Recursion naturally models inorder traversal, but iterative traversal with an explicit stack is interview-friendly and avoids deep recursion stack risk.

Brute Force and Limitations

There is no meaningful brute-force alternative; the baseline is recursive DFS. It is concise but can hit call-stack limits on extremely skewed trees.

Optimal Algorithm Steps (Iterative Stack)

1) Initialize an empty stack and pointer cur = root.
2) Push all left children of cur until cur == null.
3) Pop the top node, record its value (visit root).
4) Move cur to the popped node's right child.
5) Repeat until both cur is null and stack is empty.

Complexity Analysis

Time: O(n), each node is pushed and popped once.
Space: O(h), where h is tree height (worst O(n)).

Common Pitfalls

- Visiting node before fully going left (that becomes preorder).
- Forgetting to move to right subtree after pop.
- Using loop condition only cur != null and missing remaining stack nodes.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode cur = root;

        while (cur != null || !st.isEmpty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.left;
            }
            TreeNode node = st.pop();
            ans.add(node.val);
            cur = node.right;
        }

        return ans;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    ans := make([]int, 0)
    stack := make([]*TreeNode, 0)
    cur := root

    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }

        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        ans = append(ans, node.Val)
        cur = node.Right
    }

    return ans
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        vector<TreeNode*> st;
        TreeNode* cur = root;

        while (cur || !st.empty()) {
            while (cur) {
                st.push_back(cur);
                cur = cur->left;
            }
            TreeNode* node = st.back();
            st.pop_back();
            ans.push_back(node->val);
            cur = node->right;
        }

        return ans;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left

            node = stack.pop()
            ans.append(node.val)
            cur = node.right

        return ans

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var inorderTraversal = function(root) {
  const ans = [];
  const stack = [];
  let cur = root;

  while (cur !== null || stack.length) {
    while (cur !== null) {
      stack.push(cur);
      cur = cur.left;
    }

    const node = stack.pop();
    ans.push(node.val);
    cur = node.right;
  }

  return ans;
};

中文

题目概述

给定一棵二叉树的根节点 root，返回其中序遍历结果（左 -> 根 -> 右）。

核心思路

递归是最直观写法；但在面试和工程里，显式栈的迭代写法更可控，也能避免极端深树的递归栈风险。

基线解法与不足

基线是递归 DFS，代码短但依赖系统调用栈，遇到极端单链树时可能触发栈深限制。

最优算法步骤（迭代 + 栈）

1）准备空栈，指针 cur = root。
2）不断把当前节点及其左链入栈，直到 cur == null。
3）弹出栈顶节点，记录其值（访问“根”）。
4）令 cur 指向该节点右子树。
5）重复直到 cur 为空且栈也为空。

复杂度分析

时间复杂度：O(n)（每个节点进栈出栈各一次）。
空间复杂度：O(h)（树高，最坏 O(n)）。

常见陷阱

- 没有先一路向左到底就访问节点，顺序会错成先序。
- 弹栈后忘记转向右子树。
- 外层循环条件只写 cur != null，会漏掉栈里待处理节点。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode cur = root;

        while (cur != null || !st.isEmpty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.left;
            }
            TreeNode node = st.pop();
            ans.add(node.val);
            cur = node.right;
        }

        return ans;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    ans := make([]int, 0)
    stack := make([]*TreeNode, 0)
    cur := root

    for cur != nil || len(stack) > 0 {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }

        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        ans = append(ans, node.Val)
        cur = node.Right
    }

    return ans
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        vector<TreeNode*> st;
        TreeNode* cur = root;

        while (cur || !st.empty()) {
            while (cur) {
                st.push_back(cur);
                cur = cur->left;
            }
            TreeNode* node = st.back();
            st.pop_back();
            ans.push_back(node->val);
            cur = node->right;
        }

        return ans;
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        stack = []
        cur = root

        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left

            node = stack.pop()
            ans.append(node.val)
            cur = node.right

        return ans

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var inorderTraversal = function(root) {
  const ans = [];
  const stack = [];
  let cur = root;

  while (cur !== null || stack.length) {
    while (cur !== null) {
      stack.push(cur);
      cur = cur.left;
    }

    const node = stack.pop();
    ans.push(node.val);
    cur = node.right;
  }

  return ans;
};