Problem Description

You are given the root of a binary tree. Your task is to return the values of all nodes in the tree using inorder traversal.

Inorder traversal is a way to visit all nodes in a binary tree following this specific order:

1. First, visit all nodes in the left subtree
2. Then, visit the root node
3. Finally, visit all nodes in the right subtree

This pattern is applied recursively to every node in the tree. For each node encountered, you follow the same left-root-right pattern.

For example, if you have a binary tree like this:

    1
     \
      2
     /
    3

The inorder traversal would visit the nodes in this sequence:

• Start at root (1), go to left subtree (empty)
• Visit root (1)
• Go to right subtree (2)
• At node 2, go to left subtree (3)
• At node 3, left is empty, visit 3, right is empty
• Back to node 2, visit 2
• Right subtree of 2 is empty

So the result would be [1, 3, 2].

The function should return a list containing all the node values in the order they were visited during the inorder traversal. If the tree is empty (root is None), return an empty list.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure, which is a hierarchical data structure with a root node and child nodes.

DFS

• Yes: Since we identified this as a tree problem, the flowchart leads us directly to DFS (Depth-First Search).

Conclusion: The flowchart suggests using DFS (Depth-First Search) for traversing the binary tree. This makes perfect sense for inorder traversal because:

1. We need to visit nodes in a specific order (left subtree → root → right subtree)
2. We need to go deep into the left subtree first before processing the current node
3. The recursive nature of DFS naturally handles the nested structure of the tree
4. DFS allows us to maintain the call stack to remember which nodes to visit after completing subtree traversals

The solution implements DFS through recursion, where the function calls itself for the left subtree, processes the current node, then calls itself for the right subtree - perfectly matching the inorder traversal pattern.

Intuition

When we think about traversing a binary tree in a specific order, we need to consider how to systematically visit every node exactly once. The inorder traversal follows a "left-root-right" pattern, which means for any given node, we must:

1. First completely process everything in its left subtree
2. Then process the node itself
3. Finally process everything in its right subtree

This naturally suggests a recursive approach because the same pattern applies at every level of the tree. Each subtree is itself a tree that needs to be traversed in the same manner.

The key insight is that we can use the function call stack to our advantage. When we make a recursive call to traverse the left subtree, the current node's information is automatically saved on the call stack. After the left subtree is fully processed and that recursive call returns, we're back at the current node and can process it. Then we make another recursive call for the right subtree.

Think of it like reading a book with nested chapters:

• Before reading a chapter (visiting a node), you must read all its sub-chapters on the left
• Then read the current chapter
• Finally read all sub-chapters on the right

The base case is straightforward: when we encounter a None node (empty subtree), we simply return without doing anything. This stops the recursion from going infinitely deep.

By maintaining a shared list ans that collects node values in the order we visit them, we build up our final result. Each time we "visit" a node (after traversing its left subtree), we append its value to this list. The recursion ensures nodes are visited in the correct inorder sequence.

Learn more about Stack, Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution implements recursive traversal to visit all nodes in the binary tree following the inorder pattern (left-root-right).

Implementation Details:

The solution uses a helper function dfs nested inside the main function. This design allows the helper function to access the ans list without passing it as a parameter in every recursive call.

Algorithm Steps:

1. Initialize the result list: Create an empty list ans to store the node values in traversal order.

2. Define the recursive DFS function:

   def dfs(root):
       if root is None:
           return
       dfs(root.left)
       ans.append(root.val)
       dfs(root.right)

3. Base Case: When root is None, the function returns immediately. This handles empty trees and leaf nodes' null children.

4. Recursive Cases:

   • dfs(root.left): First, recursively traverse the entire left subtree. This ensures all nodes in the left subtree are processed before the current node.
   • ans.append(root.val): After the left subtree is complete, visit the current node by adding its value to the result list.
   • dfs(root.right): Finally, recursively traverse the entire right subtree.

5. Start the traversal: Call dfs(root) with the tree's root node to begin the traversal.

6. Return the result: Return the ans list containing all node values in inorder sequence.

Why This Works:

The recursion naturally maintains the correct order through the call stack. When we call dfs(root.left), the current function pauses, and all nodes in the left subtree get processed completely before returning to append the current node's value. This ensures the left-root-right order is preserved at every level of the tree.

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, due to the recursion call stack. In the worst case (skewed tree), this could be O(n).

Example Walkthrough

Let's walk through the solution with a concrete example to see how the recursive inorder traversal works step by step.

Consider this binary tree:

      4
     / \
    2   6
   / \
  1   3

We want to get the inorder traversal: [1, 2, 3, 4, 6]

Step-by-step execution:

1. Start: Call dfs(4) with root node 4

   • Before visiting 4, we must traverse its left subtree
   • Call dfs(2)

2. At node 2:

   • Before visiting 2, traverse its left subtree
   • Call dfs(1)

3. At node 1:

   • Call dfs(None) for left child → returns immediately
   • Visit node 1: ans = [1]
   • Call dfs(None) for right child → returns immediately
   • Return to node 2

4. Back at node 2:

   • Left subtree complete
   • Visit node 2: ans = [1, 2]
   • Call dfs(3) for right subtree

5. At node 3:

   • Call dfs(None) for left child → returns immediately
   • Visit node 3: ans = [1, 2, 3]
   • Call dfs(None) for right child → returns immediately
   • Return to node 2, then to node 4

6. Back at node 4:

   • Left subtree complete
   • Visit node 4: ans = [1, 2, 3, 4]
   • Call dfs(6) for right subtree

7. At node 6:

   • Call dfs(None) for left child → returns immediately
   • Visit node 6: ans = [1, 2, 3, 4, 6]
   • Call dfs(None) for right child → returns immediately
   • Return to node 4

8. Complete: Return ans = [1, 2, 3, 4, 6]

The key insight is how the recursion stack maintains the correct order. Each dfs(root.left) call must fully complete before we append the current node's value, ensuring all left descendants are processed first. The same pattern applies at every level, naturally producing the inorder sequence.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs an inorder traversal of the binary tree using depth-first search (DFS). Each node in the tree is visited exactly once. During each visit, the algorithm performs constant-time operations: checking if the node is None, appending the node's value to the result list, and making recursive calls. Since we visit all n nodes exactly once and perform O(1) operations at each node, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of two components:

1. Recursive call stack: In the worst case (a skewed tree), the recursion depth can be O(n), requiring O(n) stack space. In the best case (a balanced tree), the recursion depth would be O(log n).
2. Output array: The ans list stores all n node values, requiring O(n) space.

Since the output array always requires O(n) space regardless of tree structure, and the call stack can also require up to O(n) space in the worst case, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Result List in Multiple Recursive Paths

A common mistake is trying to return and concatenate lists at each recursive call instead of using a shared result list:

Incorrect Approach:

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if root is None:
        return []
  
    # This creates many intermediate lists and concatenations
    left_result = self.inorderTraversal(root.left)
    current = [root.val]
    right_result = self.inorderTraversal(root.right)
  
    return left_result + current + right_result

Issues with this approach:

• Creates many intermediate lists, increasing space complexity
• List concatenation operations add overhead
• Less efficient than appending to a single list

Solution: Use a shared result list with a helper function (as shown in the correct implementation) or pass the list as a parameter.

2. Forgetting the Base Case

Incorrect Code:

def traverse_inorder(node):
    # Missing base case check!
    traverse_inorder(node.left)  # This will fail when node is None
    result.append(node.val)
    traverse_inorder(node.right)

Issue: This causes an AttributeError when trying to access node.left on a None object.

Solution: Always check if the node is None before accessing its properties:

def traverse_inorder(node):
    if node is None:
        return
    # Rest of the code...

3. Using Global Variables Instead of Encapsulation

Problematic Pattern:

result = []  # Global variable

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        global result
        result = []  # Need to reset for each test case
        self.traverse(root)
        return result

Issues:

• Global state persists between function calls
• Can cause incorrect results when the function is called multiple times
• Makes the code harder to test and debug

Solution: Keep the result list local to the function scope using nested functions or instance variables.

4. Incorrect Traversal Order

Common Mistake:

def traverse_inorder(node):
    if node is None:
        return
  
    result.append(node.val)      # Processing node BEFORE left subtree
    traverse_inorder(node.left)   # This would be preorder, not inorder!
    traverse_inorder(node.right)

Issue: This implements preorder traversal (root-left-right) instead of inorder (left-root-right).

Solution: Ensure the correct order:

1. Process left subtree first
2. Process current node
3. Process right subtree last

5. Not Handling Edge Cases Properly

Incomplete Implementation:

def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    result = []
  
    def traverse(node):
        traverse(node.left)  # What if root itself is None?
        result.append(node.val)
        traverse(node.right)
  
    traverse(root)
    return result

Issue: Doesn't handle the case where the root itself is None (empty tree).

Solution: Either check root before calling the helper function or handle None in the helper function itself:

def traverse(node):
    if node is None:  # Handles both empty tree and leaf nodes
        return
    # Rest of the traversal logic