💬 Discord
Sign In
NeetCode #382LC-94EasyTreesNC 250
← Back to All Problems

#382 · #94 · Binary Tree Inorder Traversal(二叉树的中序遍历)

📌 Problem Statement & Constraints

Given the root of a binary tree, return its in-order traversal (left, root, right) as a list of values. Constraints: the number of nodes is in [0, 100]. The follow-up asks for an iterative solution.

💡 Core Algorithmic Approaches

  1. The iterative form uses an explicit stack: descend to the leftmost node, pushing as you go.
  2. Pop and visit, then move to the right child and repeat the descent.
  3. The loop continues while either the stack is non-empty or the current pointer is non-null.
  4. This is the same skeleton used for the K-th smallest element in a BST and for the BST iterator.

💻 Benchmark Python3 Implementation

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        st = []
        cur = root
        while cur or st:
            while cur:                     # descend to the leftmost node
                st.append(cur)
                cur = cur.left
            cur = st.pop()                 # visit
            res.append(cur.val)
            cur = cur.right                # then the right subtree
        return res


# Morris traversal: O(1) space using temporary threads
class Solution2:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        cur = root
        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
            else:
                # find the in-order predecessor
                pred = cur.left
                while pred.right and pred.right is not cur:
                    pred = pred.right
                if not pred.right:
                    pred.right = cur       # create a temporary thread
                    cur = cur.left
                else:
                    pred.right = None      # remove the thread
                    res.append(cur.val)
                    cur = cur.right
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) for both variants (Morris is O(n) amortised despite the inner loop).
💾 Space Complexity
O(h) for the stack; O(1) for Morris traversal.

⚠️ Interview Pitfalls & Follow-ups

  • Looping only while cur: nodes left on the stack after the left descent would be skipped; the condition must be while cur or st.
  • Forgetting cur = cur.right: the traversal would revisit the same node indefinitely.
  • Using recursion for a deep tree: the stack depth can reach n.
  • Morris traversal forgetting to remove the temporary thread: the tree would be corrupted and the traversal would loop.