Inorder Traversal

Inorder Traversal#

Introduction #

Inorder traversal is a depth-first traversal method used in binary trees where nodes are visited in the following order:

Traverse the left subtree in Inorder.
Visit the root.
Traverse the right subtree in Inorder.

The process is as follows:

Visit the left subtree: The traversal begins with the left subtree, following the same set of rules: visiting its left child, then the root, and finally its right child. If the left subtree is empty, this step is skipped.
Visit the root node: After the left subtree has been completely traversed, the algorithm visits the root node of the current subtree.
Visit the right subtree: After visiting the root node, the traversal moves to the right subtree and applies the same set of rules: visiting its left child, then the root, and finally its right child. If the right subtree is empty, this step is skipped.

As with postorder traversal, the traversal of the left and right subtrees involves recursion, applying the same three steps to each subtree visited. The recursion continues until a leaf node is reached, marking the base case for the recursion.

Example #

For our example tree:

      1
   __/ \_
  2      6
 / \    / \
3   4  7   9
   /  /
  5  8

The order of nodes visited during a inorder traversal of this tree is:

3-2-5-4-8-1-7-6-9

Here’s how you’d perform an inorder traversal on this example tree::

Visit all nodes in the left subtree of 1:
- Visit all nodes in the left subtree of 2:
  - Visit all nodes in the left subtree of 3. The left subtree of 3 is None, so there are no nodes to visit.
  - Visit the root of this subtree: 3.
  - Visit all nodes in the right subtree of 3. The right subtree of 3 is None, so there are no nodes to visit.
- Visit the root of the left subtree: 2.
- Visit all nodes in the right subtree of 2:
  - Visit all nodes in the left subtree of 4.
    - Visit the root of this subtree: 5.
      - Visit all nodes in the left subtree of 5. The left subtree of 5 is None, so there are no nodes to visit.
      - Visit the root of this subtree: 5.
      - Visit all nodes in the right subtree of 5. The right subtree of 5 is None, so there are no nodes to visit.
  - Visit the root of this subtree: 4.
  - Visit all nodes in the right subtree of 4. The right subtree of 4 is None, so there are no nodes to visit.
Visit the root node: 1.
Visit all nodes in the right subtree of 1:
- Visit all nodes in the left subtree of 6:
  - Visit all nodes in the left subtree of 7.
    - Visit the root of this subtree: 8.
      - Visit all nodes in the left subtree of 8. The left subtree of 8 is None, so there are no nodes to visit.
      - Visit the root of this subtree: 8.
      - Visit all nodes in the right subtree of 8. The right subtree of 8 is None, so there are no nodes to visit.
  - Visit the root of this subtree: 7.
  - Visit all nodes in the right subtree of 7. The right subtree of 7 is None, so there are no nodes to visit.
- Visit the root of the right subtree: 6.
- Visit all nodes in the right subtree of 6:
  - Visit all nodes in the left subtree of 9. The left subtree of 9 is None, so there are no nodes to visit.
  - Visit the root of this subtree: 9.
  - Visit all nodes in the right subtree of 9. The right subtree of 9 is None, so there are no nodes to visit.
Now that all nodes in the left and right subtrees of 1 have been visited and 1 itself has been visited, the traversal is complete.

Therefore, the order of nodes visited during an in-order traversal of this tree is 3-2-5-4-1-8-7-6-9. The process is recursive, and the same set of rules is applied to each subtree within the tree. As with preorder, any recursive process can also be implemented iteratively; we can implement an in-order traversal of a binary tree iteratively using a stack.

Visualization #

See leetcode’s visualization of Inorder.

Problem #

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Intuition #

In an in-order traversal, the intuition can be understood through the family gathering analogy again, but this time with a different rule of introduction.

Parents tell children: “Before I introduce myself, I will ask my left child (if any) to introduce themselves first, along with their own children (if any), following the same rule. Only after the entire left subtree has been introduced will I introduce myself. Then, if I have a right child, I will ask them to do the same thing: introduce themselves and their own children (if any), in the same order. This ensures that the right subtree introductions happen after I introduce myself.”
Children follow their parent’s instructions: Each child node in the tree considers itself as the root of its own subtree. They first ask their left child (if any) to introduce themselves, then they introduce themselves, and finally, they ask their right child (if any) to introduce themselves, following the same rules.

In essence, each node in the tree, whether a parent or a child, follows the same process: they let their left subtree (if it exists) “introduce” themselves first, then they “introduce” themselves, and finally, they let their right subtree (if it exists) “introduce” themselves.

This parent-child communication continues until all nodes in the tree have been visited, ensuring a complete In-order Traversal of the tree.

So in an In-order traversal, a node’s left subtree corresponds to everyone who introduces themselves before it, the node itself is the one introducing themselves now, and the right subtree corresponds to everyone who introduces themselves after it.

Assumptions #

The input is a binary tree where a node can have at most two children.
The binary tree does not have to be balanced.
The binary tree can be empty, which means the root can be None.
- So make sure to handle this edge case in your code!
Each node contains an integer value.

Constraints #

The number of nodes in the tree is in the range:

\[ 0 \leq \text{number of nodes} \leq 100 \]

This constraint specifies the minimum and maximum size of the binary tree that our algorithm needs to handle. Knowing this, we can evaluate whether our solution would scale efficiently for the largest possible input size. For example, a solution with a time complexity of \(\mathcal{O}(n)\), where \(n\) is the number of nodes in the tree, would likely be acceptable.
Each node’s value is an integer in the range:

\[ -100 \leq \text{Node.val} \leq 100 \]

This constraint informs us about the range of values that each node in the tree can hold. It is important to take this into account when considering possible edge cases. However, for this particular problem of preorder traversal, the actual values of the nodes do not affect the traversal order.

What are Constraints for?#

In programming problems, constraints are given to define the scope and limits of the problem. They help to determine the feasible approaches and solutions for the problem by providing information about the range and characteristics of the input data. They help us anticipate the worst-case scenarios that our algorithm should be able to handle without leading to inefficiencies or failures, like time limit exceeded or memory limit exceeded errors.

Test Cases #

Normal case: A tree with more than one node.

The list represents a binary tree as follows:

root = build_binary_tree_from_list_preorder(
    [1, 2, 4, None, None, 5, None, None, 3, 6, None, None, 7, None, None]
)
assert inorder_traversal(root) == [4, 2, 5, 1, 6, 3, 7]

Unbalanced tree: A tree where one side has more nodes than the other side.

root = build_binary_tree_from_list_preorder([1, 2, 3, None, 4, None, None, None, None])
assert inorder_traversal(root) == [4, 3, 2, 1]

Tree with single path: A tree where each parent has only one child.

root = build_binary_tree_from_list_preorder([1, 2, 3, None, 4, None, None, None, None])
assert inorder_traversal(root) == [4, 3, 2, 1]

Tree with duplicate values: A tree with duplicate values in nodes.

root = build_binary_tree_from_list_preorder([1, 1, 1, None, 1, None, 1, None, None, None, None])
assert inorder_traversal(root) == [1, 1, 1, 1, 1]

Edge Cases #

Empty tree: A tree with no nodes. This is a valid input and should return an empty list.

root = build_binary_tree_from_list_preorder([])
assert inorder_traversal(root) == []

Single node: A tree with only one node. This edge case tests whether the function can handle the smallest non-empty tree.
```
root = build_binary_tree_from_list_preorder([1])
assert inorder_traversal(root) == [1]
```
Tree with maximum allowed nodes: This edge case tests if the function can handle the largest possible tree within the constraints. Given the constraint that each node’s value is unique, the input list will follow the pattern of descending to the leftmost node and then filling in the right subtree at each level before moving down to the next level.
```
root = build_binary_tree_from_list_preorder(list(range(1, 101)))
# Depends on the structure of the tree.
assert inorder_traversal(root) == list(range(1, 101))
```
Tree with minimum and maximum allowed node values: This edge case tests if the function can handle the smallest and largest possible node values within the constraints.
```
root = build_binary_tree_from_list_preorder([-100, None, 100])
assert inorder_traversal(root) == [-100, 100]
```

Walkthrough / Whiteboarding #

The whiteboarding and complexity analysis for in-order traversal will be very similar to the one we provided for preorder traversal. The primary difference will be the order in which nodes are visited and added to the output list.

Consider the binary tree below:

The in-order traversal sequence for this tree is 4, 2, 5, 1, 3.

First, traverse the left subtree of root node 1. Visit 2, then go left and visit 4.
For 4, the left and right are None, so we return to 2.
Since we are done with the left subtree of 2, we visit 2, then go right and visit 5.
Similarly, for 5, the left and right are None, so we return to 2, and then since we are done with 2, we return to 1.
Now we visit the root node 1 as we’ve completed the left subtree.
Next, we traverse the right subtree. Visit 3.
No more nodes left to visit, hence the traversal is complete.

Theoretical Best Time Complexity #

The theoretical best time complexity for in-order traversal of a binary tree is \(\mathcal{O}(n)\), where \(n\) is the number of nodes in the binary tree. This is because each node is visited exactly once during the traversal.

See preorder traversal for a detailed explanation of why the time complexity is \(\mathcal{O}(n)\).

Theoretical Best Space Complexity #

The theoretical best (auxiliary) space complexity for this problem is \(\mathcal{O}(n)\), where \(n\) is the number of nodes in the binary tree. This is due to the space required by the call stack (assuming a recursive implementation), which grows proportional to the maximum height of the tree (which in worst case could be \(n\)), and the space required to store the output, which would be equal to the number of nodes in the binary tree.

Space-Time Tradeoff #

As with preorder traversal, there isn’t much of a traditional space-time tradeoff in this problem. The traversal is a linear operation with respect to the number of nodes, and the space required is also proportional to the number of nodes. The most efficient solution will always involve visiting each node in the tree once, and the space used is necessary to store the output and accommodate the recursion stack (in case of recursive approach). However, an iterative solution using an explicit stack would have the same space complexity due to the need for storing nodes in a stack data structure.

Solution (Recursive)#

Implementation #

class Solution1:
    def inorderTraversal(self, root: Optional[BinaryTreeNode]) -> List[int]:
        inorder: List[int] = []

        def traverse(root: Optional[BinaryTreeNode], inorder: List[int]) -> List[int]:
            if not root:
                return inorder

            traverse(root.left, inorder)
            inorder.append(root.value)
            traverse(root.right, inorder)
            return inorder

        inorder = traverse(root, inorder)
        return inorder

class Solution2:
    def __init__(self) -> None:
        self.inorder: List[int] = []

    def reset(self) -> None:
        """To reset if the class instance were to traverse a new root."""
        self.inorder = []

    def inorderTraversal(self, root: Optional[BinaryTreeNode]) -> List[int]:
        if not root:
            return

        self.inorderTraversal(root.left)
        self.inorder.append(root.value)
        self.inorderTraversal(root.right)

        return self.inorder

Tests #

inorder_traversal = Solution1().inorderTraversal

def print_and_test_inorder(
    root: Optional[BinaryTreeNode],
    expected_output: List[int],
    case_name: str,
    print_tree: bool = True,
):
    if print_tree:
        print(case_name)
        lines = print_binary_tree(
            root, node_info=lambda n: (str(n.value), n.left, n.right), is_top=False
        )
        print("\n".join(lines))
    compare_test_case(inorder_traversal(root), expected_output, case_name)


# Test Case 1: Normal case
print_and_test_inorder(
    build_binary_tree_from_list_preorder(
        [1, 2, 4, None, None, 5, None, None, 3, 6, None, None, 7, None, None]
    ),
    [4, 2, 5, 1, 6, 3, 7],
    "Normal case",
)

# Test Case 2: Unbalanced tree
print_and_test_inorder(
    build_binary_tree_from_list_preorder([1, 2, 3, None, 4, None, None, None, None]),
    [3, 4, 2, 1],
    "Unbalanced tree",
)

# Test Case 3: Tree with single path
print_and_test_inorder(
    build_binary_tree_from_list_preorder([1, 2, 3, None, 4, None, None, None, None]),
    [3, 4, 2, 1],
    "Tree with single path",
)

# Test Case 4: Tree with duplicate values
print_and_test_inorder(
    build_binary_tree_from_list_preorder([1, 1, 1, None, 1, None, 1, None, None, None, None]),
    [1, 1, 1, 1, 1],
    "Tree with duplicate values",
)

# Edge Case 1: Empty tree
print_and_test_inorder(build_binary_tree_from_list_preorder([]), [], "Empty tree", print_tree=False)

# Edge Case 2: Single node
print_and_test_inorder(build_binary_tree_from_list_preorder([1]), [1], "Single node")

# Edge Case 3: Tree with maximum allowed nodes
print_and_test_inorder(
    build_binary_tree_from_list_preorder(list(range(1, 101))),
    list(range(100, 0, -1)),
    "Tree with maximum allowed nodes",
    print_tree=False,
)

# Edge Case 4: Tree with minimum and maximum allowed node values
print_and_test_inorder(
    build_binary_tree_from_list_preorder([-100, None, 100]),
    [-100, 100],
    "Tree with minimum and maximum allowed node values",
)

Normal case
      1
   __/ \_
  2      3
 / \    / \
4   5  6   7

Test passed: Normal case

Unbalanced tree
    1
   /
  2
 /
3
 \
  4

Test passed: Unbalanced tree

Tree with single path
    1
   /
  2
 /
3
 \
  4

Test passed: Tree with single path

Tree with duplicate values
    1
   /
  1
 /
1
 \
  1
   \
    1

Test passed: Tree with duplicate values

Test passed: Empty tree

Single node
1

Test passed: Single node

Test passed: Tree with maximum allowed nodes

Tree with minimum and maximum allowed node values
-100
   \
   100

Test passed: Tree with minimum and maximum allowed node values

Time Complexity #

In the case of inorder traversal, the time and space complexity would be the same as for preorder traversal. This is because the order in which the nodes are visited (preorder, inorder, or postorder) does not change the amount of work to be done or the space required. The only difference is the order in which the nodes are added to the output list.

The time complexity of inorder traversal, like preorder and postorder traversals, is \(\mathcal{O}(n)\), where \(n\) is the number of nodes. This is because the algorithm must visit every node in the tree once and only once.

Table 81 Time Complexity of Inorder Traversal Recursive Algorithm#
Case	Worst Case	Average Case	Best Case
Empty Tree	\(\mathcal{O}(1)\)	\(\mathcal{O}(1)\)	\(\mathcal{O}(1)\)
Balanced Tree	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)
Degenerate Tree	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)
Random Tree	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)

If you want to see a more detailed analysis of the time complexity of inorder, see my post on preorder.

Table 82 Auxiliary Space Complexity of Inorder Traversal Recursive Algorithm#
Case	Auxiliary Space Complexity
Empty Tree	\(\mathcal{O}(1)\)
Balanced Tree	\(\mathcal{O}(\log n)\)
Degenerate Tree	\(\mathcal{O}(n)\)

Total Space Complexity #

The total space complexity, which includes both the input and auxiliary space complexities, is as follows:

Table 83 Total Space Complexity of Inorder Traversal Recursive Algorithm#
Case	Total Space Complexity
Empty Tree	\(\mathcal{O}(1)\)
Balanced Tree	\(\mathcal{O}(n)\)
Degenerate Tree	\(\mathcal{O}(n)\)

Leetcode Solution
Leetcode Card: Traverse a Tree
Tree Traversal Time Complexity
Time Complexity of Binary Tree Preorder