Tree Traversal: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Tree Traversal: Complete Guide with Examples and Complexity

Welcome to the practice problems for tree traversal. If you need a refresher on the code, the code templates have the recursive and iterative versions in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution. The solutions assume the TreeNode class from the template page, which is exactly what LeetCode provides in its editor.

Recommended Study Order

Start with Binary Tree Inorder Traversal to lock in the recursive skeleton, since every depth-first solution on this page is that skeleton with one line moved. Maximum Depth adds the postorder idea of combining subtree results. Level Order introduces the queue and the size snapshot, and Zigzag layers a direction toggle onto it. Validate BST shows why inorder is the default for anything involving BSTs. Finish with Maximum Path Sum and Serialize, which combine the traversals with genuinely tricky edge cases like negative values and null markers.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Binary Tree Inorder Traversal

LeetCode 94 | Difficulty: Easy

Brief: Return the inorder traversal of a binary tree’s node values.

Why this pattern: This is the fundamental recursive skeleton. Recurse left, process the node, recurse right. Nothing else happens.

Key Insight: For a BST the same function returns values in sorted order, which makes this the building block for validation and kth-smallest problems.

Visual:

    flowchart LR
    subgraph Tree["Input tree"]
        A((1)) --> B((2))
        A --> C((3))
    end
    subgraph Order["Visit order"]
        S1["1. Left subtree: 2"]
        S2["2. Root: 1"]
        S3["3. Right subtree: 3"]
    end
    Tree --> Order

Complexity: Time

O(N)

| Space

O(H)

Code:

var inorderTraversal = function(root) {
    const result = [];

    function inorder(node) {
        if (!node) return;

        // Left subtree, then the node, then the right
        // subtree. For a BST this is sorted order.
        inorder(node.left);
        result.push(node.val);
        inorder(node.right);
    }

    inorder(root);
    return result;
};

from typing import List, Optional

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []

        def inorder(node):
            if not node:
                return

            inorder(node.left)
            result.append(node.val)
            inorder(node.right)

        inorder(root)
        return result

import java.util.*;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    private void inorder(TreeNode node, List<Integer> result) {
        if (node == null) return;

        inorder(node.left, result);
        result.add(node.val);
        inorder(node.right, result);
    }
}

#include <vector>

class Solution {
public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> result;
        inorder(root, result);
        return result;
    }

private:
    void inorder(TreeNode* node, std::vector<int>& result) {
        if (!node) return;

        inorder(node->left, result);
        result.push_back(node->val);
        inorder(node->right, result);
    }
};

func inorderTraversal(root *TreeNode) []int {
    result := []int{}

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        inorder(node.Left)
        result = append(result, node.Val)
        inorder(node.Right)
    }

    inorder(root)
    return result
}

def inorder_traversal(root)
  result = []

  inorder = ->(node) {
    return if node.nil?

    inorder.call(node.left)
    result << node.val
    inorder.call(node.right)
  }

  inorder.call(root)
  result
end

This is the main template applied directly. The base case returns without appending, so empty subtrees contribute nothing, and the recursive calls guarantee every node lands in the result exactly once. If you can write this function from memory, preorder and postorder are a one-line move away.

2. Maximum Depth of Binary Tree

LeetCode 104 | Difficulty: Easy

Brief: Return the maximum depth, defined as the number of nodes along the longest root-to-leaf path.

Why this pattern: The depth of a node is one plus the maximum depth of its children. The children must be answered before the parent, which is the postorder shape.

Key Insight: The base case is depth 0 for a null subtree. That single value propagates up through every level.

Visual:

    flowchart TD
    subgraph Tree["Tree with subtree depths"]
        A((3)) --> B((9))
        A --> C((20))
        C --> D((15))
        C --> E((7))
    end
    A -. "1 + max(1, 2)" .-> R["Max depth = 3"]

Complexity: Time

O(N)

| Space

O(H)

Code:

var maxDepth = function(root) {
    if (!root) return 0;

    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);

    // The node adds one level on top of the deeper
    // of its two subtrees.
    return 1 + Math.max(leftDepth, rightDepth);
};

from typing import Optional

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)

        # Add one for this node on top of the deeper subtree.
        return 1 + max(left_depth, right_depth)

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        // Add one for this node on top of the deeper subtree.
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

#include <algorithm>

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        // Add one for this node on top of the deeper subtree.
        return 1 + std::max(leftDepth, rightDepth);
    }
};

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)

    // Add one for this node on top of the deeper subtree.
    if leftDepth > rightDepth {
        return 1 + leftDepth
    }
    return 1 + rightDepth
}

def max_depth(root)
  return 0 if root.nil?

  left_depth = max_depth(root.left)
  right_depth = max_depth(root.right)

  # Add one for this node on top of the deeper subtree.
  1 + [left_depth, right_depth].max
end

The recursion returns a number instead of appending to a list, but the shape is the same postorder walk. Each node waits for both children, combines their answers with max, and adds one for itself. The space is O(H) because the call stack holds one frame per level.

Medium Problems

3. Binary Tree Level Order Traversal

LeetCode 102 | Difficulty: Medium

Brief: Return node values level by level, each level as its own list.

Why this pattern: Level-order is BFS on a tree. A queue holds the current frontier, and a size snapshot separates levels.

Key Insight: Children pushed during the loop belong to the next level. Snapshot the queue length once, before the inner loop.

Visual:

    flowchart TD
    subgraph Tree["Input tree"]
        A((3)) --> B((9))
        A --> C((20))
        C --> D((15))
        C --> E((7))
    end
    subgraph Output["Level lists"]
        L1["Level 0: [3]"]
        L2["Level 1: [9, 20]"]
        L3["Level 2: [15, 7]"]
    end
    Tree --> Output

Complexity: Time

O(N)

| Space

O(N)

Code:

var levelOrder = function(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];

    while (queue.length) {
        // Snapshot the size. Children added during this
        // level belong to the next one.
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(currentLevel);
    }

    return result;
};

from typing import List, Optional
from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = deque([root])

        while queue:
            # Only the nodes already in the queue belong to
            # this level. Children wait for the next pass.
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(current_level)

        return result

import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            result.add(currentLevel);
        }

        return result;
    }
}

#include <vector>
#include <queue>

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> result;
        if (!root) return result;

        std::queue<TreeNode*> queue;
        queue.push(root);

        while (!queue.empty()) {
            int levelSize = queue.size();
            std::vector<int> currentLevel;

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                currentLevel.push_back(node->val);
                if (node->left) queue.push(node->left);
                if (node->right) queue.push(node->right);
            }

            result.push_back(currentLevel);
        }

        return result;
    }
};

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    result := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        currentLevel := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            currentLevel = append(currentLevel, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, currentLevel)
    }

    return result
}

def level_order(root)
  return [] if root.nil?

  result = []
  queue = [root]

  until queue.empty?
    level_size = queue.length
    current_level = []

    level_size.times do
      node = queue.shift
      current_level << node.val
      queue << node.left if node.left
      queue << node.right if node.right
    end

    result << current_level
  end

  result
end

The levelSize snapshot is the whole trick. Without it the inner loop would absorb the next level as children get enqueued, and the output would come back as one flat list. The queue itself holds at most one full level, which is why the space is O(N) in the worst case.

4. Validate Binary Search Tree

LeetCode 98 | Difficulty: Medium

Brief: Determine whether a binary tree is a valid BST, meaning every left subtree holds smaller values and every right subtree holds larger ones.

Why this pattern: Inorder traversal of a valid BST produces strictly increasing values. Check each node against the previous one instead of building the whole list.

Key Insight: A node with value equal to the previous one is invalid, so the comparison must be strict. Storing the full traversal wastes space when one variable does the job.

Visual:

    flowchart TD
    subgraph Valid["Valid BST"]
        A1((5)) --> B1((3))
        A1 --> C1((7))
    end
    subgraph Invalid["Not a BST"]
        A2((5)) --> B2((6))
        A2 --> C2((7))
    end
    Valid --> V1["Inorder: 3, 5, 7 - increasing"]
    Invalid --> V2["Inorder: 6, 5, 7 - not increasing"]

Complexity: Time

O(N)

| Space

O(H)

Code:

var isValidBST = function(root) {
    let prev = -Infinity;

    function inorder(node) {
        if (!node) return true;

        // The left subtree must already be valid before
        // we compare the current node against the previous.
        if (!inorder(node.left)) return false;

        if (node.val <= prev) return false;
        prev = node.val;

        return inorder(node.right);
    }

    return inorder(root);
};

from typing import Optional

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        prev = float('-inf')

        def inorder(node):
            nonlocal prev
            if not node:
                return True

            if not inorder(node.left):
                return False

            # Strictly greater is required. Equal values
            # mean the tree is not a valid BST.
            if node.val <= prev:
                return False
            prev = node.val

            return inorder(node.right)

        return inorder(root)

class Solution {
    // Long instead of int so the first node can safely
    // be Integer.MIN_VALUE without failing the check.
    private long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }

    private boolean inorder(TreeNode node) {
        if (node == null) return true;

        if (!inorder(node.left)) return false;

        if (node.val <= prev) return false;
        prev = node.val;

        return inorder(node.right);
    }
}

#include <climits>

class Solution {
private:
    long long prev = LLONG_MIN;

public:
    bool isValidBST(TreeNode* root) {
        return inorder(root);
    }

private:
    bool inorder(TreeNode* node) {
        if (!node) return true;

        if (!inorder(node->left)) return false;

        if (node->val <= prev) return false;
        prev = node->val;

        return inorder(node->right);
    }
};

import "math"

func isValidBST(root *TreeNode) bool {
    prev := math.MinInt64

    var inorder func(node *TreeNode) bool
    inorder = func(node *TreeNode) bool {
        if node == nil {
            return true
        }

        // The left subtree must already be valid before
        // we compare the current node against the previous.
        if !inorder(node.Left) {
            return false
        }

        if node.Val <= prev {
            return false
        }
        prev = node.Val

        return inorder(node.Right)
    }

    return inorder(root)
}

def is_valid_bst(root)
  @prev = -Float::INFINITY

  inorder = ->(node) {
    return true if node.nil?

    return false unless inorder.call(node.left)

    return false if node.val <= @prev
    @prev = node.val

    inorder.call(node.right)
  }

  inorder.call(root)
end

The previous value is initialized to negative infinity so the first node always passes. Java and C++ use the wider Long.MIN_VALUE and LLONG_MIN instead of the int versions, because the first node could legitimately be Integer.MIN_VALUE and the comparison would fail. The strict check is what rejects trees with duplicate values.

5. Binary Tree Zigzag Level Order Traversal

LeetCode 103 | Difficulty: Medium

Brief: Return level-order traversal where the direction alternates, left to right on even levels and right to left on odd ones.

Why this pattern: This is level-order with a direction flag. The BFS structure is unchanged.

Key Insight: Collect each level normally, then reverse every other level. No other change is needed.

Visual:

    flowchart TD
    subgraph Tree["Input tree"]
        A((3)) --> B((9))
        A --> C((20))
        C --> D((15))
        C --> E((7))
    end
    subgraph Output["Zigzag output"]
        L1["Level 0, left to right: [3]"]
        L2["Level 1, right to left: [20, 9]"]
        L3["Level 2, left to right: [15, 7]"]
    end
    Tree --> Output

Complexity: Time

O(N)

| Space

O(N)

Code:

var zigzagLevelOrder = function(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];
    let leftToRight = true;

    while (queue.length) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        // Reverse odd levels so the direction alternates.
        if (!leftToRight) {
            currentLevel.reverse();
        }

        result.push(currentLevel);
        leftToRight = !leftToRight;
    }

    return result;
};

from typing import List, Optional
from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = deque([root])
        left_to_right = True

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # Reverse odd levels so the direction alternates.
            if not left_to_right:
                current_level.reverse()

            result.append(current_level)
            left_to_right = not left_to_right

        return result

import java.util.*;

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            // Reverse odd levels so the direction alternates.
            if (!leftToRight) {
                Collections.reverse(currentLevel);
            }

            result.add(currentLevel);
            leftToRight = !leftToRight;
        }

        return result;
    }
}

#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root) {
        std::vector<std::vector<int>> result;
        if (!root) return result;

        std::queue<TreeNode*> queue;
        queue.push(root);
        bool leftToRight = true;

        while (!queue.empty()) {
            int levelSize = queue.size();
            std::vector<int> currentLevel;

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                currentLevel.push_back(node->val);
                if (node->left) queue.push(node->left);
                if (node->right) queue.push(node->right);
            }

            // Reverse odd levels so the direction alternates.
            if (!leftToRight) {
                std::reverse(currentLevel.begin(), currentLevel.end());
            }

            result.push_back(currentLevel);
            leftToRight = !leftToRight;
        }

        return result;
    }
};

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    result := [][]int{}
    queue := []*TreeNode{root}
    leftToRight := true

    for len(queue) > 0 {
        levelSize := len(queue)
        currentLevel := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            currentLevel = append(currentLevel, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        // Reverse odd levels so the direction alternates.
        if !leftToRight {
            for i, j := 0, len(currentLevel)-1; i < j; i, j = i+1, j-1 {
                currentLevel[i], currentLevel[j] = currentLevel[j], currentLevel[i]
            }
        }

        result = append(result, currentLevel)
        leftToRight = !leftToRight
    }

    return result
}

def zigzag_level_order(root)
  return [] if root.nil?

  result = []
  queue = [root]
  left_to_right = true

  until queue.empty?
    level_size = queue.length
    current_level = []

    level_size.times do
      node = queue.shift
      current_level << node.val
      queue << node.left if node.left
      queue << node.right if node.right
    end

    # Reverse odd levels so the direction alternates.
    current_level.reverse! unless left_to_right

    result << current_level
    left_to_right = !left_to_right
  end

  result
end

The reversal adds a constant amount of work per level, so the complexity is unchanged. The flag flips after every level, which means the root level is always left to right and the alternation is automatic from there.

Hard Problems

6. Binary Tree Maximum Path Sum

LeetCode 124 | Difficulty: Hard

Brief: Find the maximum sum along any path, where a path starts and ends at any nodes and follows parent-child edges.

Why this pattern: Postorder, because each node needs both subtree answers before deciding anything about itself.

Key Insight: A subtree with a negative contribution never helps any path through its parent, so negative contributions are clamped to 0. The global maximum may join the left and right branches through the current node, while the value returned upward can only use one branch.

Visual:

    flowchart TD
    A(("-10")) --> B((9))
    A --> C((20))
    C --> D((15))
    C --> E((7))
    A -. "best path" .-> P["15 -> 20 -> 7, sum 42"]

Complexity: Time

O(N)

| Space

O(H)

Code:

var maxPathSum = function(root) {
    let maxSum = -Infinity;

    function dfs(node) {
        if (!node) return 0;

        // Clamp negative contributions to 0. A subtree
        // that drags the sum down should not join any path.
        const left = Math.max(0, dfs(node.left));
        const right = Math.max(0, dfs(node.right));

        // A path may bend through this node, joining both
        // branches. Only the global maximum sees this.
        maxSum = Math.max(maxSum, node.val + left + right);

        // The parent can only use one branch, so return
        // the better side plus this node's value.
        return node.val + Math.max(left, right);
    }

    dfs(root);
    return maxSum;
};

from typing import Optional

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        max_sum = float('-inf')

        def dfs(node):
            nonlocal max_sum
            if not node:
                return 0

            # Clamp negative contributions to 0 so a
            # subtree never drags a path down.
            left = max(0, dfs(node.left))
            right = max(0, dfs(node.right))

            # A path may bend through this node, joining
            # both branches. Only the global maximum sees it.
            max_sum = max(max_sum, node.val + left + right)

            # The parent can only use one branch.
            return node.val + max(left, right)

        dfs(root)
        return max_sum

class Solution {
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;

        // Clamp negative contributions to 0 so a subtree
        // never drags a path down.
        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));

        // A path may bend through this node, joining both
        // branches. Only the global maximum sees this.
        maxSum = Math.max(maxSum, node.val + left + right);

        // The parent can only use one branch.
        return node.val + Math.max(left, right);
    }
}

#include <algorithm>
#include <climits>

class Solution {
private:
    int maxSum = INT_MIN;

public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return maxSum;
    }

private:
    int dfs(TreeNode* node) {
        if (!node) return 0;

        // Clamp negative contributions to 0 so a subtree
        // never drags a path down.
        int left = std::max(0, dfs(node->left));
        int right = std::max(0, dfs(node->right));

        // A path may bend through this node, joining both
        // branches. Only the global maximum sees this.
        maxSum = std::max(maxSum, node->val + left + right);

        // The parent can only use one branch.
        return node->val + std::max(left, right);
    }
};

import "math"

func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt32

    var dfs func(node *TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        // Clamp negative contributions to 0 so a subtree
        // never drags a path down.
        left := max(0, dfs(node.Left))
        right := max(0, dfs(node.Right))

        // A path may bend through this node, joining both
        // branches. Only the global maximum sees this.
        if node.Val+left+right > maxSum {
            maxSum = node.Val + left + right
        }

        // The parent can only use one branch.
        return node.Val + max(left, right)
    }

    dfs(root)
    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

def max_path_sum(root)
  @max_sum = -Float::INFINITY

  dfs = ->(node) {
    return 0 if node.nil?

    # Clamp negative contributions to 0 so a subtree
    # never drags a path down.
    left = [0, dfs.call(node.left)].max
    right = [0, dfs.call(node.right)].max

    # A path may bend through this node, joining both
    # branches. Only the global maximum sees this.
    @max_sum = [@max_sum, node.val + left + right].max

    # The parent can only use one branch.
    node.val + [left, right].max
  }

  dfs.call(root)
  @max_sum
end

Each node returns the best single-branch contribution it can offer its parent, which is its value plus the better of the two clamped child contributions. The global maximum is updated separately, because a path that bends through the node cannot continue upward. Clamping to 0 is what lets a negative subtree disappear instead of dragging every path down.

7. Serialize and Deserialize Binary Tree

LeetCode 297 | Difficulty: Hard

Brief: Encode a binary tree into a string and rebuild the exact same tree from that string.

Why this pattern: Preorder with explicit null markers captures the complete structure, because every node arrives before its children and every missing child is recorded.

Key Insight: Without null markers, a node with only a right child is indistinguishable from a node with only a left child. Mark every null child so the rebuild never guesses.

Visual:

    flowchart LR
    subgraph Tree["Binary tree"]
        A((1)) --> B((2))
        A --> C((3))
        C --> D((4))
        C --> E((5))
    end
    subgraph Encoded["Encoded string"]
        S1["1,2,null,null,3,4,null,null,5,null,null"]
    end
    Tree -->|serialize| Encoded
    Encoded -->|deserialize| Tree

Complexity: Time

O(N)

| Space

O(N)

Code:

var serialize = function(root) {
    const result = [];

    function dfs(node) {
        if (!node) {
            result.push('null');
            return;
        }
        result.push(String(node.val));
        dfs(node.left);
        dfs(node.right);
    }

    dfs(root);
    return result.join(',');
};

var deserialize = function(data) {
    const values = data.split(',');
    let index = 0;

    function dfs() {
        if (values[index] === 'null') {
            index++;
            return null;
        }

        const node = new TreeNode(parseInt(values[index]));
        index++;
        node.left = dfs();
        node.right = dfs();
        return node;
    }

    return dfs();
};

class Codec:
    def serialize(self, root):
        result = []

        def dfs(node):
            if not node:
                result.append('null')
                return
            result.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ','.join(result)

    def deserialize(self, data):
        values = data.split(',')
        self.index = 0

        def dfs():
            if values[self.index] == 'null':
                self.index += 1
                return None

            node = TreeNode(int(values[self.index]))
            self.index += 1
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()

import java.util.*;

public class Codec {
    private int index;

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("null,");
            return;
        }
        sb.append(node.val).append(",");
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }

    public TreeNode deserialize(String data) {
        String[] values = data.split(",");
        index = 0;
        return deserializeHelper(values);
    }

    private TreeNode deserializeHelper(String[] values) {
        if (values[index].equals("null")) {
            index++;
            return null;
        }

        TreeNode node = new TreeNode(Integer.parseInt(values[index]));
        index++;
        node.left = deserializeHelper(values);
        node.right = deserializeHelper(values);
        return node;
    }
}

#include <string>
#include <sstream>
#include <vector>

class Codec {
public:
    std::string serialize(TreeNode* root) {
        std::string result;
        serializeHelper(root, result);
        return result;
    }

    TreeNode* deserialize(std::string data) {
        std::vector<std::string> values;
        std::stringstream ss(data);
        std::string item;
        while (std::getline(ss, item, ',')) {
            values.push_back(item);
        }
        int index = 0;
        return deserializeHelper(values, index);
    }

private:
    void serializeHelper(TreeNode* node, std::string& result) {
        if (!node) {
            result += "null,";
            return;
        }
        result += std::to_string(node->val) + ",";
        serializeHelper(node->left, result);
        serializeHelper(node->right, result);
    }

    TreeNode* deserializeHelper(std::vector<std::string>& values, int& index) {
        if (values[index] == "null") {
            index++;
            return nullptr;
        }

        TreeNode* node = new TreeNode(std::stoi(values[index]));
        index++;
        node->left = deserializeHelper(values, index);
        node->right = deserializeHelper(values, index);
        return node;
    }
};

import (
    "strconv"
    "strings"
)

type Codec struct{}

func (c *Codec) serialize(root *TreeNode) string {
    var result []string

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            result = append(result, "null")
            return
        }
        result = append(result, strconv.Itoa(node.Val))
        dfs(node.Left)
        dfs(node.Right)
    }

    dfs(root)
    return strings.Join(result, ",")
}

func (c *Codec) deserialize(data string) *TreeNode {
    values := strings.Split(data, ",")
    index := 0

    var dfs func() *TreeNode
    dfs = func() *TreeNode {
        if values[index] == "null" {
            index++
            return nil
        }

        val, _ := strconv.Atoi(values[index])
        node := &TreeNode{Val: val}
        index++
        node.Left = dfs()
        node.Right = dfs()
        return node
    }

    return dfs()
}

class Codec
  def serialize(root)
    result = []

    dfs = ->(node) {
      if node.nil?
        result << 'null'
        return
      end
      result << node.val.to_s
      dfs.call(node.left)
      dfs.call(node.right)
    }

    dfs.call(root)
    result.join(',')
  end

  def deserialize(data)
    values = data.split(',')
    @index = 0

    dfs = -> {
      if values[@index] == 'null'
        @index += 1
        return nil
      end

      node = TreeNode.new(values[@index].to_i)
      @index += 1
      node.left = dfs.call
      node.right = dfs.call
      node
    }

    dfs.call
  end
end

The serialize pass is preorder with “null” appended for missing children. Deserialize walks the same sequence in the same order, consuming one token for every node or null marker. The shared index guarantees the two passes mirror each other exactly. Space is O(N) because the string holds one token per node plus one per null child.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These seven problems cover both traversal families. Start with the recursive skeleton in Inorder and Max Depth, pick up the queue in Level Order and Zigzag, and finish with the postorder reasoning in Max Path Sum and the preorder encoding in Serialize. By the end, the question of which order a problem needs should answer itself in the first minute of any tree problem.

Done with these problems? The app has more, plus a review system that brings problems back right before you would forget them. Continue your prep .