C# LeetCode 94: Binary Tree Inorder Traversal - (Easy)

Problem

Given the root of a binary tree, return the "inorder traversal" of its node's values.

Approach

Firstly, you're maybe thinking what is inorder traversal ? Well it means:

For each node:

1. Visit the left subtree first
2. Then visit the current node
3. Then visit the right subtree

Example:

        6
       / \
      4   8
     / \   \
    3   5   9
   /
  1

In‑order traversal steps:

1. Start at root 6 → go left to 4
2. From 4 → go left to 3
3. From 3 → go left to 1 → visit 1 (no left child)
4. Back to 3 → visit 3 → no right child → back to 4
5. Visit 4 → go right to 5 → visit 5 → back to 6
6. Visit 6 → go right to 8
7. From 8 → no left child → visit 8 → go right to 9 → visit 9

So we go as far left as we can before returning back up the branch and going right, until we try to get left again as far as we can and so on.

We achieve this using a Stack which works on a LIFO (last in first out) approach.

1. We keep going left, pushing nodes onto the stack.

2. When you can’t go left anymore, Pop() from the stack, visit the node and move to its right child.

3. Repeat until both current is null and the stack is empty.

Whatever result we have at the end is our inorder-traversal of our binary tree.

Code

public IList<int> InorderTraversal(TreeNode root) {

    var result = new List<int>();
    var stack = new Stack<TreeNode>();
    var current = root;

    while (current != null || stack.Count > 0)
    {
        while (current != null)
        {
            stack.Push(current);
            current = current.left;
        }

        current = stack.Pop();
        result.Add(current.val);
        current = current.right;
    }

    return result.ToArray();
}