Start learning free

LESSON 309 OF 347 · BINARY TREES

Inorder Traversal in C#: Recursive DFS on a Binary Tree

Practice O(n) Read the full explanation

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1, 3, 2]

Follow up: Recursive solution is trivial, could you do it iteratively?

STEP 1 OF 8
    Ctrl + Enter to check

    C# · BINARY TREES

    Inorder Traversal in C#, explained

    Problem overview

    The method InorderTraversal receives the root of a binary tree and returns a List<int> with the node values in order: the whole left subtree, then the node, then the whole right subtree.

    In the example, the root 1 has only a right child, 2, and 2 has a left child 3. The root has no left subtree, so 1 comes first. Then the right subtree is traversed in order: 3 is the left child of 2, so 3 comes before 2. The output is [1, 3, 2].

    Approach: left, node, right

    The definition of the order is already recursive: to traverse a tree in order, traverse its left subtree in order, record the node, and traverse its right subtree in order. An empty subtree contributes nothing, which gives the base case.

    The lesson passes one shared list through all the calls. Each call adds its node to that list at the right moment, so no lists have to be combined. The statement's follow up mentions an iterative version, which uses an explicit stack. This lesson is the recursive one, which is short and a good first version.

    In a binary search tree, in order traversal returns the values in ascending order. That is the main reason this particular order is worth knowing.

    Tracing the example

    The calls on [1, null, 2, 3] run in this order:

    1. Dfs(1) calls Dfs(null) for its left side, which returns at once.
    2. Dfs(1) adds 1, so the list is [1].
    3. Dfs(1) calls Dfs(2) for its right side. That call goes left first, into Dfs(3).
    4. Dfs(3) finds two missing children, adds 3, and returns. The list is [1, 3].
    5. Dfs(2) adds 2, then calls Dfs(null) for its missing right child. The list is [1, 3, 2].

    Every node is added after the calls that cover its left side and before the call that covers its right side, which is what the name "in order" describes.

    Step by step

    1. Declare the helper above InorderTraversal as public void Dfs(TreeNode root, List<int> result). It takes the root of a subtree and the list to fill.
    2. Return on null. A missing child arrives as null and adds nothing. This check also ends the recursion.
    3. Go left with Dfs(root.left, result). Every value of the left subtree is added before the current node.
    4. Add the node's value with result.Add(root.val). The node is visited after its whole left subtree.
    5. Go right with Dfs(root.right, result).
    6. In InorderTraversal, create the list with new List<int>().
    7. Call the helper with root and result.
    8. Return the list. It now holds every value in order.

    The solution in C#

    class Solution {
    public void Dfs(TreeNode root, List<int> result) {
        if (root == null) {
            return;
        }
        Dfs(root.left, result);
        result.Add(root.val);
        Dfs(root.right, result);
    }
    public List<int> InorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        Dfs(root, result);
        return result;
    }
}

    Things to notice in the C# code:

    • Shared list. List<int> is a class, so Dfs works on the caller's list rather than a copy. That is why Dfs can be void.
    • Lowercase node fields. The lesson's TreeNode exposes val, left and right. Methods such as Add are PascalCase, as are the lesson's own methods.
    • The placement of Add is the entire difference between the three depth-first orders. Here it sits between the two recursive calls.

    Complexity

    Time: O(n). Every node is visited exactly once, and each visit does constant work.

    Space: O(h) beyond the output, where h is the height of the tree, for the recursion. A balanced tree has h near log n, and a chain has h equal to n. The returned list needs n entries.

    Edge cases and common mistakes

    • Empty tree. The first call sees null and returns, so the method returns an empty list.
    • Only a right child. The left call returns at once, then the node is added, then the right subtree is processed. For the example the output starts with the root.
    • Wrong position of Add. Before the left call you get pre order, [1, 2, 3] for the example. After the right call you get post order, [3, 2, 1].
    • Forgetting the null check. Calling Dfs on a leaf's children would then read root.left on null and throw a NullReferenceException.
    • Returning a new list from every call. This works only if the lists are merged correctly. A single shared list is simpler.
    • Repeated values. The traversal works on nodes, not on values, so equal values in different nodes each appear in the output. A tree with two nodes holding 5 produces two 5s.
    • Deep chains. A tree shaped like a very long chain can overflow the call stack with recursion. The iterative approach with a stack avoids that.

    Testing

    • The tree [1, null, 2, 3] gives [1, 3, 2].
    • A single node [4] gives [4].
    • An empty tree gives [].
    • The tree [2, 1, 3] gives [1, 2, 3], sorted because it is a binary search tree.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free