Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Binary Tree Traversals

Try it yourself
EasyProblemExternal link

Description

A traversal visits every node of a binary tree exactly once, in a fixed order. There are four classic orders:

  • Preorder (node, left, right): record a node before its left and right subtrees.
  • Inorder (left, node, right): record a node between its left and right subtrees.
  • Postorder (left, right, node): record a node after both of its subtrees.
  • Level order: record the nodes row by row from the top, left to right within each row.

The first three go as deep as possible before moving sideways, so they are called depth-first traversals. Level order finishes a whole row before going deeper, so it is called breadth-first.

Given the root of a binary tree, return a list of four lists, [preorder, inorder, postorder, level order], each holding the node values in the order they are visited.

The tree is written in level order, with null for a missing child: [5, 8, 2, 1, 6, null, 9] is the tree in Example 1.

Where each order is used:

  • Preorder puts a parent before its children, so it is used to copy a tree or save it in a form that can be rebuilt.
  • Inorder visits a binary search tree's values in sorted order.
  • Postorder handles children before their parent, as when deleting a tree or adding up the sizes of subtrees.
  • Level order handles nodes by their distance from the root, for example to find the leaf closest to the top.

Examples

Example 1

Input: root = [5, 8, 2, 1, 6, null, 9]

        5
      /   \
     8     2
    / \     \
   1   6     9

Output: [[5, 8, 1, 6, 2, 9], [1, 8, 6, 5, 2, 9], [1, 6, 8, 9, 2, 5], [5, 8, 2, 1, 6, 9]]

Explanation:

  • Preorder: 5 first, then all of 8's subtree (8, 1, 6), then all of 2's subtree (2, 9).
  • Inorder: 8's subtree in order (1, 8, 6), then 5, then 2's subtree. 2 has no left child, so 2 comes before 9.
  • Postorder: 8's subtree with 8 last (1, 6, 8), then 2's subtree with 2 last (9, 2), then 5 at the very end.
  • Level order: row 0 is 5, row 1 is 8 and 2, row 2 is 1, 6 and 9.

Example 2

Input: root = [10, null, 20, 15]

  10
    \
     20
    /
  15

Output: [[10, 20, 15], [10, 15, 20], [15, 20, 10], [10, 20, 15]]

Explanation: 10 has no left subtree, so inorder records 10 first. 15 is 20's left child, so inorder puts it before 20. Postorder finishes 15, then 20, then 10. Preorder and level order happen to match here, because every row holds a single node, but in general they differ, as Example 1 shows.

Example 3

Input: root = [42]

Output: [[42], [42], [42], [42]]

Explanation: A lone node is at once first, in the middle and last, and it is the whole top row, so all four orders are [42].

Constraints

  • 0 ≤ number of nodes ≤ 500
  • −1000 ≤ Node.val ≤ 1000
  • Values may repeat

Editorial

Brute Force

Intuition

Each depth-first order has a one-line recursive definition, so the most direct plan writes each one as its own function:

  • preorder(node): record node, then preorder(left), then preorder(right).
  • inorder(node): inorder(left), then record node, then inorder(right).
  • postorder(node): postorder(left), then postorder(right), then record node.

An empty subtree records nothing, and that is what stops the recursion. For Example 1 these give preorder [5, 8, 1, 6, 2, 9], inorder [1, 8, 6, 5, 2, 9] and postorder [1, 6, 8, 9, 2, 5].

For level order, the direct idea is to answer one question per depth: which nodes sit exactly d steps below the root? A helper starts at the root, steps down d times in every possible way, and records the nodes it lands on. Doing this for d = 0, 1, 2, … up to the tree's height produces the rows in order.

The depth-first part is fine. The level-order part is where the waste hides, so that is what the walkthrough traces.

Step-by-Step Explanation

Example 1, root = [5, 8, 2, 1, 6, null, 9]:

        5
      /   \
     8     2
    / \     \
   1   6     9

Step 1: Compute the height first: 3 rows, so depths 0, 1 and 2. This walk already touches all 6 nodes.

Step 2: Depth 0. The root itself is 0 steps down, so record 5. (1 node touched.)

Step 3: Depth 1. Start again at 5 and step down once. The left step lands on 8, so record 8.

Step 4: The right step lands on 2, so record 2. (5, 8 and 2 touched.)

Step 5: Depth 2. Start again at 5, step to 8, then down to 1, and record 1.

Step 6: From 8, step down to 6 and record 6.

Step 7: Back at 5, step to 2. It has no left child, so step down to 9 and record 9. (All 6 touched.)

Step 8: Level order is [5, 8, 2, 1, 6, 9]. The root was walked through at every depth, and 8 and 2 twice each: 10 node visits to produce 6 values, on top of the height walk.

Level Order by Depth: Restarting From the Root Each Time — For each depth, walk down from the root and record the nodes found there. Amber nodes are the path walked for the current depth.

Algorithm

  1. Walk the tree three times with preorder, inorder and postorder, each recording the node at its own point.
  2. Compute h = height(root): 0 for an empty tree, otherwise 1 + the larger height of the two subtrees.
  3. For each depth from 0 to h − 1, call collect(root, depth):
    • If the node is empty, return.
    • If depth == 0, record the node.
    • Otherwise call collect(left, depth − 1), then collect(right, depth − 1).
  4. Return [preorder, inorder, postorder, level order].

Code

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> treeTraversals(TreeNode* root) {
        vector<int> pre, in, post, level;
        preorder(root, pre);
        inorder(root, in);
        postorder(root, post);
        int h = height(root);
        for (int depth = 0; depth < h; depth++) {
            collectDepth(root, depth, level);
        }
        return {pre, in, post, level};
    }

private:
    void preorder(TreeNode* node, vector<int>& out) {
        if (!node) return;
        out.push_back(node->val);  // the node comes first
        preorder(node->left, out);
        preorder(node->right, out);
    }

    void inorder(TreeNode* node, vector<int>& out) {
        if (!node) return;
        inorder(node->left, out);
        out.push_back(node->val);  // the node sits between its two subtrees
        inorder(node->right, out);
    }

    void postorder(TreeNode* node, vector<int>& out) {
        if (!node) return;
        postorder(node->left, out);
        postorder(node->right, out);
        out.push_back(node->val);  // the node comes last
    }

    int height(TreeNode* node) {
        if (!node) return 0;
        return 1 + max(height(node->left), height(node->right));
    }

    // Walks down from the root on every call, so the top of the tree is re-visited once per depth
    void collectDepth(TreeNode* node, int depth, vector<int>& out) {
        if (!node) return;
        if (depth == 0) {
            out.push_back(node->val);
            return;
        }
        collectDepth(node->left, depth - 1, out);
        collectDepth(node->right, depth - 1, out);
    }
};
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def treeTraversals(self, root: Optional[TreeNode]) -> List[List[int]]:
        pre, ino, post, level = [], [], [], []

        def preorder(node):
            if node is None:
                return
            pre.append(node.val)  # the node comes first
            preorder(node.left)
            preorder(node.right)

        def inorder(node):
            if node is None:
                return
            inorder(node.left)
            ino.append(node.val)  # the node sits between its two subtrees
            inorder(node.right)

        def postorder(node):
            if node is None:
                return
            postorder(node.left)
            postorder(node.right)
            post.append(node.val)  # the node comes last

        def height(node):
            if node is None:
                return 0
            return 1 + max(height(node.left), height(node.right))

        def collect_depth(node, depth):
            # Walks down from the root on every call, so the top of the tree is re-visited once per depth
            if node is None:
                return
            if depth == 0:
                level.append(node.val)
                return
            collect_depth(node.left, depth - 1)
            collect_depth(node.right, depth - 1)

        preorder(root)
        inorder(root)
        postorder(root)
        for depth in range(height(root)):
            collect_depth(root, depth)
        return [pre, ino, post, level]
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class Solution {
    public List<List<Integer>> treeTraversals(TreeNode root) {
        List<Integer> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>(), level = new ArrayList<>();
        preorder(root, pre);
        inorder(root, in);
        postorder(root, post);
        int h = height(root);
        for (int depth = 0; depth < h; depth++) {
            collectDepth(root, depth, level);
        }
        return Arrays.asList(pre, in, post, level);
    }

    private void preorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        out.add(node.val);  // the node comes first
        preorder(node.left, out);
        preorder(node.right, out);
    }

    private void inorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);  // the node sits between its two subtrees
        inorder(node.right, out);
    }

    private void postorder(TreeNode node, List<Integer> out) {
        if (node == null) return;
        postorder(node.left, out);
        postorder(node.right, out);
        out.add(node.val);  // the node comes last
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    // Walks down from the root on every call, so the top of the tree is re-visited once per depth
    private void collectDepth(TreeNode node, int depth, List<Integer> out) {
        if (node == null) return;
        if (depth == 0) {
            out.add(node.val);
            return;
        }
        collectDepth(node.left, depth - 1, out);
        collectDepth(node.right, depth - 1, out);
    }
}

Complexity Analysis

Time Complexity: O(n × h), which is O(n²) for a chain

Here n is the number of nodes and h the height. The three depth-first walks and the height walk each visit every node once: O(n). Collecting depth d walks through every node from the root down to that depth, so summed over all depths it costs up to n × h. In a chain, where every node has one child, h = n and the depth walks make n(n + 1)/2 visits. A 500-node chain needs about 125,000 visits to produce 500 values.

Space Complexity: O(h)

The recursion is at most h calls deep. The answer lists themselves hold 4n values.

Why This Approach Is Not Efficient

Two kinds of work are repeated:

  1. Level order walks the top of the tree again and again. Every depth restarts at the root, so a node at depth k is walked through once for its own depth and again for every deeper one. On a tall, thin tree this grows with the square of the number of nodes.
  2. The same depth-first walk happens three times. preorder, inorder and postorder all go down the same paths in the same order, and differ only in when they record a node. That is three walks where one would do.

The fixes: record all three depth-first orders during a single walk, and for level order remember the nodes that have been found but not yet visited, in a queue, so no node is ever walked through twice.

Optimal Approach - One Walk for Three Orders, Plus a Queue

Intuition

One walk, three moments. Follow a depth-first walk and watch a single node. The walk arrives at it, goes off into its left subtree, comes back, goes off into its right subtree, and comes back again. So every node is met at exactly three moments:

  1. on arrival, which is where preorder records it;
  2. back from the left subtree, which is where inorder records it;
  3. back from the right subtree, which is where postorder records it.

The three orders are the same walk with the pen put down at a different moment. So one walk can fill all three lists: add the node to pre on arrival, to in between the two recursive calls, and to post at the end.

Level order with a queue. Level order needs every node of a row before anything in the next row. Keep a queue, where the first node added is the first one taken out. Start with the root. Then repeatedly take the node at the front, record it, and add its children at the back. A row's children always join the line behind the whole row, so the rows come out in order, and left children join before right ones, so each row reads left to right. Each node joins and leaves the queue exactly once.

Think of the line at a ticket counter: everyone already standing in it is served before anyone who arrives later.

Step-by-Step Explanation

Example 1 again:

        5
      /   \
     8     2
    / \     \
   1   6     9

The walk: all three depth-first orders at once

Step 1: Arrive at 5, so pre = [5].

Step 2: Arrive at 8, so pre = [5, 8].

Step 3: Arrive at 1, so pre = [5, 8, 1].

Step 4: Back from the left of 1, so in = [1].

Step 5: Back from the right of 1, so post = [1].

Step 6: Back from the left of 8, so in = [1, 8].

Step 7: Arrive at 6, so pre = [5, 8, 1, 6].

Step 8: Back from the left of 6, so in = [1, 8, 6].

Step 9: Back from the right of 6, so post = [1, 6].

Step 10: Back from the right of 8, so post = [1, 6, 8].

Step 11: Back from the left of 5, so in = [1, 8, 6, 5].

Step 12: Arrive at 2, so pre = [5, 8, 1, 6, 2].

Step 13: Back from the left of 2, so in = [1, 8, 6, 5, 2].

Step 14: Arrive at 9, so pre = [5, 8, 1, 6, 2, 9].

Step 15: Back from the left of 9, so in = [1, 8, 6, 5, 2, 9].

Step 16: Back from the right of 9, so post = [1, 6, 8, 9].

Step 17: Back from the right of 2, so post = [1, 6, 8, 9, 2].

Step 18: Back from the right of 5, so post = [1, 6, 8, 9, 2, 5].

After 18 moments, three per node: preorder [5, 8, 1, 6, 2, 9], inorder [1, 8, 6, 5, 2, 9], postorder [1, 6, 8, 9, 2, 5].

The queue: level order

Step 19: Start with queue = [5].

Step 20: Take 5 and record it. Add 8 and 2, so queue = [8, 2].

Step 21: Take 8 and record it. Add 1 and 6, so queue = [2, 1, 6].

Step 22: Take 2 and record it. It has no left child, so add only 9: queue = [1, 6, 9].

Step 23: Take 1 and record it. It is a leaf, so queue = [6, 9].

Step 24: Take 6 and record it, leaving queue = [9].

Step 25: Take 9 and record it. The queue is empty.

Step 26: Level order is [5, 8, 2, 1, 6, 9]. That is 6 visits, where the depth-by-depth version needed 10 plus the height walk.

One Walk, Three Moments — The walk meets every node three times. Amber is the path from the root to the current node, teal nodes are finished, and each list grows only at its own moment.

Level Order With a Queue — Take the front of the queue, record it, and add its children at the back. Amber nodes are waiting in the queue, teal nodes are recorded.

Algorithm

  1. Create empty lists pre, in and post.
  2. Define walk(node):
    • If node is empty, return.
    • Add node to pre, then call walk(left).
    • Add node to in, then call walk(right).
    • Add node to post.
  3. Call walk(root).
  4. For level order: if root is not empty, put it in a queue. While the queue is not empty, take the front node, add it to level, then add its left child and its right child, if they exist, to the back.
  5. Return [pre, in, post, level].

Code

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> treeTraversals(TreeNode* root) {
        vector<int> pre, in, post, level;
        walk(root, pre, in, post);

        queue<TreeNode*> q;
        if (root) q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();  // the oldest discovered node goes first
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return {pre, in, post, level};
    }

private:
    void walk(TreeNode* node, vector<int>& pre, vector<int>& in, vector<int>& post) {
        if (!node) return;
        pre.push_back(node->val);   // moment 1: just arrived
        walk(node->left, pre, in, post);
        in.push_back(node->val);    // moment 2: back from the left subtree
        walk(node->right, pre, in, post);
        post.push_back(node->val);  // moment 3: back from the right subtree
    }
};
from collections import deque
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def treeTraversals(self, root: Optional[TreeNode]) -> List[List[int]]:
        pre, ino, post = [], [], []

        def walk(node):
            if node is None:
                return
            pre.append(node.val)   # moment 1: just arrived
            walk(node.left)
            ino.append(node.val)   # moment 2: back from the left subtree
            walk(node.right)
            post.append(node.val)  # moment 3: back from the right subtree

        walk(root)

        level = []
        queue = deque([root] if root else [])
        while queue:
            node = queue.popleft()  # the oldest discovered node goes first
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return [pre, ino, post, level]
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class Solution {
    private final List<Integer> pre = new ArrayList<>(), in = new ArrayList<>(), post = new ArrayList<>();

    public List<List<Integer>> treeTraversals(TreeNode root) {
        walk(root);

        List<Integer> level = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();  // the oldest discovered node goes first
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return Arrays.asList(pre, in, post, level);
    }

    private void walk(TreeNode node) {
        if (node == null) return;
        pre.add(node.val);   // moment 1: just arrived
        walk(node.left);
        in.add(node.val);    // moment 2: back from the left subtree
        walk(node.right);
        post.add(node.val);  // moment 3: back from the right subtree
    }
}

Complexity Analysis

Time Complexity: O(n)

The walk meets each node three times and does constant work each time. Every node joins and leaves the queue once. Both parts are linear, however the tree is shaped.

Space Complexity: O(h + w)

The recursion is at most h calls deep, where h is the height. The queue only ever holds nodes from two neighbouring rows, so it stays O(w), where w is the widest row. The answer itself holds 4n values. With at most 500 nodes, even a chain only recurses 500 deep, which every language handles. Much taller trees need an explicit stack instead of recursion, which the next problems in this section teach: Preorder, Inorder and Postorder with a stack, and All Three Traversals in one pass.

Comparison:

ApproachPasses over the treeTimeExtra space
Separate walks3 depth-first + height + one per depthO(n × h), O(n²) for a chainO(h)
One walk + queue1 depth-first + 1 queue passO(n)O(h + w)