Start learning free

LESSON 335 OF 414 · BINARY TREES

Inorder Traversal in Rust: 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,None,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

    RUST · BINARY TREES

    Inorder Traversal in Rust, explained

    Problem overview

    The function inorder_traversal receives the root of a binary tree, an Option<Box<TreeNode>>, and returns the values of all nodes as a Vec<i32> in inorder: the whole left subtree first, then the node itself, then the whole right subtree.

    In the example, node 1 has no left child and has node 2 as its right child, and node 2 has node 3 as its left child. The traversal visits 1 first, because its left subtree is empty. Then it enters the right subtree rooted at 2, where the left child 3 comes before 2 itself. The result is [1, 3, 2].

    Approach: let recursion follow the shape of the tree

    A tree is a node with two smaller trees attached, so the definition of inorder is already recursive. To traverse a tree: traverse its left subtree, record the node, traverse its right subtree. An empty tree is the base case and records nothing.

    In a binary search tree this order yields the values sorted ascending, which is the main reason inorder is worth knowing. The other two depth-first orders only move the "record the node" step: before both subtrees is preorder, after both is postorder.

    The statement's follow-up asks for an iterative version. This lesson does the recursive one, which is short enough to write from the definition. The iterative idea is mentioned at the end.

    Step by step

    1. Write the helper dfs. It takes the root of a subtree, as an Option<Box<TreeNode>>, and a &mut Vec<i32> named result. The mutable reference lets every recursive call push into the same vector, so nothing has to be merged afterwards. The helper has no self, so it is called as Self::dfs.
    2. Unwrap the root with if let Some(node). When the subtree is empty the pattern doesn't match, the block is skipped, and the function returns. That is the base case.
    3. Recurse into the left subtree with node.left.
    4. Push node.val into result.
    5. Recurse into the right subtree with node.right. The three steps in this order are what make it inorder.
    6. In inorder_traversal, create an empty result vector with let mut, call Self::dfs(root, &mut result) and return result.

    The solution in Rust

    impl Solution {
    fn inorder_traversal(root: Option<Box<TreeNode>>) -> Vec<i32> {
        let mut result = Vec::new();
        Self::dfs(root, &mut result);
        result
    }

    fn dfs(root: Option<Box<TreeNode>>, result: &mut Vec<i32>) {
        if let Some(node) = root {
            Self::dfs(node.left, result);
            result.push(node.val);
            Self::dfs(node.right, result);
        }
    }
}

    The Rust details worth a closer look:

    • Ownership moves down the tree. dfs takes root by value, so it owns that subtree. Passing node.left moves the left child out of the box into the recursive call, and node.right does the same later. node.val is an i32, which is copied, so reading it between the two moves is fine. The tree is consumed by the traversal, and the caller can't use it afterwards.
    • &mut Vec<i32> is passed on as it is. result is already a mutable reference inside dfs, so the recursive calls take result, not &mut result. Rust reborrows it for each call, which is why the same reference can be used again afterwards.
    • The type of Vec::new() is inferred. The call to dfs says the vector holds i32, and the function returns a Vec<i32>, so no annotation is needed.
    • Order of definition doesn't matter. dfs is written below the function that calls it. Inside an impl block, methods and associated functions can be declared in any order.
    • Final expression. The last line result has no semicolon, so it is returned.

    Complexity

    Time: O(n) for n nodes. Each node is visited once, and each visit does a constant amount of work. The calls on empty subtrees add at most n + 1 more constant-time calls.

    Space: O(h) for the call stack, where h is the height of the tree, plus O(n) for the result itself. A balanced tree has h near log n. A tree that is a single chain has h equal to n, and a very long chain makes the recursion very deep.

    Edge cases and common mistakes

    • Empty tree. None returns an empty vector.
    • Only left children. A chain 5, 4, 3, 2 going down the left side gives [2, 3, 4, 5]: the deepest node is reported first.
    • Wrong order of the three steps. Pushing the value first gives preorder and pushing it last gives postorder. For the example tree those are [1, 2, 3] and [3, 2, 1].
    • Returning a new vector from each call. It works, but it copies values at every level. Passing one &mut Vec avoids that.
    • Using node after moving its children. After node.left and node.right have been moved, only the fields that were not moved can still be used. val is never moved, since it is copied.

    The iterative idea

    The recursion's call stack can be replaced by a Vec used as a stack. Walk down the left edge, pushing each node. Then pop a node, record its value, and continue with its right child. Repeat until the current subtree is empty and the stack is empty. On the same example this also returns [1, 3, 2], and it keeps the depth on the heap instead of the call stack.

    Testing

    • Root 1 with right child 2, whose left child is 3: [1, 3, 2].
    • Root 4 with children 2 and 6, whose children are 1, 3, 5 and 7: [1, 2, 3, 4, 5, 6, 7].
    • An empty tree: [].
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free