Coding Patterns
Tree Traversal
Problems

Problems

Master tree traversal by solving these carefully selected LeetCode problems. Each problem builds on the concepts from the Concept Guide and uses patterns from the Code Templates.

Easy

1. Binary Tree Inorder Traversal

  • Brief: Given the root of a binary tree, return the inorder traversal of its nodes’ values.
  • Why this pattern?: This is the fundamental inorder traversal: visit left subtree, process node, visit right subtree.
  • Key Insight: For BSTs, inorder traversal produces sorted output.
  flowchart LR
    subgraph Tree["Input Tree"]
        A((1))
        B((2))
        C((3))
        A --> B
        A --> C
    end

    subgraph Output["Inorder Output"]
        O1["[2, 1, 3]"]
    end

    Tree --> Output

Complexity: Time

O(N)
| Space
O(H)

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

    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        result.push(node.val);
        inorder(node.right);
    }

    inorder(root);
    return result;
}
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

def inorderTraversal(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

2. Binary Tree Preorder Traversal

  • Brief: Given the root of a binary tree, return the preorder traversal of its nodes’ values.
  • Why this pattern?: Preorder visits root first, then left, then right. Useful for copying trees.
  • Key Insight: The first element is always the root.
  flowchart LR
    subgraph Tree["Input Tree"]
        A((1))
        B((2))
        C((3))
        A --> B
        A --> C
    end

    subgraph Output["Preorder Output"]
        O1["[1, 2, 3]"]
    end

    Tree --> Output

Complexity: Time

O(N)
| Space
O(H)

function preorderTraversal(root) {
    const result = [];

    function preorder(node) {
        if (!node) return;
        result.push(node.val);
        preorder(node.left);
        preorder(node.right);
    }

    preorder(root);
    return result;
}
from typing import List, Optional

def preorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []

    def preorder(node):
        if not node:
            return
        result.append(node.val)
        preorder(node.left)
        preorder(node.right)

    preorder(root)
    return result
import java.util.*;

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

    private void preorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        result.add(node.val);
        preorder(node.left, result);
        preorder(node.right, result);
    }
}
#include <vector>

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

private:
    void preorder(TreeNode* node, std::vector<int>& result) {
        if (!node) return;
        result.push_back(node->val);
        preorder(node->left, result);
        preorder(node->right, result);
    }
};
func preorderTraversal(root *TreeNode) []int {
    result := []int{}

    var preorder func(node *TreeNode)
    preorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        result = append(result, node.Val)
        preorder(node.Left)
        preorder(node.Right)
    }

    preorder(root)
    return result
}
def preorder_traversal(root)
  result = []

  preorder = ->(node) {
    return if node.nil?
    result << node.val
    preorder.call(node.left)
    preorder.call(node.right)
  }

  preorder.call(root)
  result
end

3. Maximum Depth of Binary Tree

  • Brief: Given the root of a binary tree, return its maximum depth.
  • Why this pattern?: Use postorder traversal to calculate depth from leaves up to root.
  • Key Insight: Max depth = 1 + max(left depth, right depth).
  flowchart TD
    subgraph Tree["Input Tree"]
        A((3))
        B((9))
        C((20))
        D((15))
        E((7))

        A --> B
        A --> C
        C --> D
        C --> E
    end

    subgraph Result["Result"]
        R1["Max Depth = 3"]
    end

Complexity: Time

O(N)
| Space
O(H)

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

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

    return 1 + Math.max(leftDepth, rightDepth);
}
from typing import Optional

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

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

    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);

        return 1 + Math.max(leftDepth, rightDepth);
    }
}
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;

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

        return 1 + std::max(leftDepth, rightDepth);
    }
};
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

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

    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)

  1 + [left_depth, right_depth].max
end

4. Same Tree

  • Brief: Given the roots of two binary trees, check if they are the same.
  • Why this pattern?: Use preorder traversal to compare corresponding nodes simultaneously.
  • Key Insight: Both structure and values must match at every position.
  flowchart LR
    subgraph Tree1["Tree 1"]
        A1((1))
        B1((2))
        C1((3))
        A1 --> B1
        A1 --> C1
    end

    subgraph Tree2["Tree 2"]
        A2((1))
        B2((2))
        C2((3))
        A2 --> B2
        A2 --> C2
    end

    subgraph Result["Result"]
        R1["true"]
    end

    Tree1 --> Result
    Tree2 --> Result

Complexity: Time

O(N)
| Space
O(H)

function isSameTree(p, q) {
    // Both null: same
    if (!p && !q) return true;
    // One null: different
    if (!p || !q) return false;
    // Values differ: different
    if (p.val !== q.val) return false;

    // Recursively check left and right subtrees
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
from typing import Optional

def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    # Both null: same
    if not p and not q:
        return True
    # One null: different
    if not p or not q:
        return False
    # Values differ: different
    if p.val != q.val:
        return False

    # Recursively check left and right subtrees
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // Both null: same
        if (p == null && q == null) return true;
        // One null: different
        if (p == null || q == null) return false;
        // Values differ: different
        if (p.val != q.val) return false;

        // Recursively check left and right subtrees
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // Both null: same
        if (!p && !q) return true;
        // One null: different
        if (!p || !q) return false;
        // Values differ: different
        if (p->val != q->val) return false;

        // Recursively check left and right subtrees
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};
func isSameTree(p *TreeNode, q *TreeNode) bool {
    // Both null: same
    if p == nil && q == nil {
        return true
    }
    // One null: different
    if p == nil || q == nil {
        return false
    }
    // Values differ: different
    if p.Val != q.Val {
        return false
    }

    // Recursively check left and right subtrees
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
def is_same_tree(p, q)
  # Both null: same
  return true if p.nil? && q.nil?
  # One null: different
  return false if p.nil? || q.nil?
  # Values differ: different
  return false if p.val != q.val

  # Recursively check left and right subtrees
  is_same_tree(p.left, q.left) && is_same_tree(p.right, q.right)
end

Medium

5. Binary Tree Level Order Traversal

  • Brief: Given the root of a binary tree, return the level order traversal of its nodes’ values.
  • Why this pattern?: Classic BFS using a queue to process nodes level by level.
  • Key Insight: Track level size before processing to separate levels.
  flowchart TD
    subgraph Tree["Input Tree"]
        A((3))
        B((9))
        C((20))
        D((15))
        E((7))

        A --> B
        A --> C
        C --> D
        C --> E
    end

    subgraph Output["Level Order Output"]
        L1["Level 0: [3]"]
        L2["Level 1: [9, 20]"]
        L3["Level 2: [15, 7]"]
    end

Complexity: Time

O(N)
| Space
O(N)

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

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

    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);
        }

        result.push(currentLevel);
    }

    return result;
}
from typing import List, Optional
from collections import deque

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

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

    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)

        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

6. Validate Binary Search Tree

  • Brief: Given the root of a binary tree, determine if it is a valid BST.
  • Why this pattern?: Inorder traversal of a valid BST produces strictly increasing values.
  • Key Insight: Track the previous value and ensure current is always greater.
  flowchart TD
    subgraph ValidBST["Valid BST"]
        A1((5))
        B1((3))
        C1((7))
        A1 --> B1
        A1 --> C1
    end

    subgraph InvalidBST["Invalid BST"]
        A2((5))
        B2((6))
        C2((7))
        A2 --> B2
        A2 --> C2
    end

    subgraph Results["Results"]
        R1["Inorder: 3,5,7 - Valid"]
        R2["Inorder: 6,5,7 - Invalid"]
    end

Complexity: Time

O(N)
| Space
O(H)

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

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

        // Check left subtree
        if (!inorder(node.left)) return false;

        // Check current node against previous
        if (node.val <= prev) return false;
        prev = node.val;

        // Check right subtree
        return inorder(node.right);
    }

    return inorder(root);
}
from typing import Optional

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

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

        # Check left subtree
        if not inorder(node.left):
            return False

        # Check current node against previous
        if node.val <= prev:
            return False
        prev = node.val

        # Check right subtree
        return inorder(node.right)

    return inorder(root)
class Solution {
    private long prev = Long.MIN_VALUE;

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

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

        // Check left subtree
        if (!inorder(node.left)) return false;

        // Check current node against previous
        if (node.val <= prev) return false;
        prev = node.val;

        // Check right subtree
        return inorder(node.right);
    }
}
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;

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

        // Check current node against previous
        if (node->val <= prev) return false;
        prev = node->val;

        // Check right subtree
        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
        }

        // Check left subtree
        if !inorder(node.Left) {
            return false
        }

        // Check current node against previous
        if node.Val <= prev {
            return false
        }
        prev = node.Val

        // Check right subtree
        return inorder(node.Right)
    }

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

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

    # Check left subtree
    return false unless inorder.call(node.left)

    # Check current node against previous
    return false if node.val <= @prev
    @prev = node.val

    # Check right subtree
    inorder.call(node.right)
  }

  inorder.call(root)
end

7. Binary Tree Zigzag Level Order Traversal

  • Brief: Return the zigzag level order traversal (alternating left-to-right and right-to-left).
  • Why this pattern?: BFS with direction tracking. Reverse alternate levels.
  • Key Insight: Use a flag to toggle direction after each level.
  flowchart TD
    subgraph Tree["Input Tree"]
        A((3))
        B((9))
        C((20))
        D((15))
        E((7))

        A --> B
        A --> C
        C --> D
        C --> E
    end

    subgraph Output["Zigzag Output"]
        L1["Level 0 L->R: [3]"]
        L2["Level 1 R->L: [20, 9]"]
        L3["Level 2 L->R: [15, 7]"]
    end

Complexity: Time

O(N)
| Space
O(N)

function zigzagLevelOrder(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);
        }

        if (!leftToRight) {
            currentLevel.reverse();
        }

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

    return result;
}
from typing import List, Optional
from collections import deque

def zigzagLevelOrder(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)

        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);
            }

            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);
            }

            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)
            }
        }

        if !leftToRight {
            // Reverse the slice
            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

    current_level.reverse! unless left_to_right

    result << current_level
    left_to_right = !left_to_right
  end

  result
end

Hard

8. Binary Tree Maximum Path Sum

  • Brief: Find the maximum path sum of any non-empty path in the tree.
  • Why this pattern?: Postorder traversal to calculate max contribution from each subtree.
  • Key Insight: At each node, the path can go through it. Track global max separately.
  flowchart TD
    subgraph Tree["Input Tree"]
        A(("-10"))
        B((9))
        C((20))
        D((15))
        E((7))

        A --> B
        A --> C
        C --> D
        C --> E
    end

    subgraph Calculation["Max Path"]
        R1["Path: 15 -> 20 -> 7"]
        R2["Sum: 42"]
    end

Complexity: Time

O(N)
| Space
O(H)

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

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

        // Get max contribution from left and right (ignore negative)
        const left = Math.max(0, dfs(node.left));
        const right = Math.max(0, dfs(node.right));

        // Path through current node
        const currentPathSum = node.val + left + right;
        maxSum = Math.max(maxSum, currentPathSum);

        // Return max contribution to parent
        return node.val + Math.max(left, right);
    }

    dfs(root);
    return maxSum;
}
from typing import Optional

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

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

        # Get max contribution from left and right (ignore negative)
        left = max(0, dfs(node.left))
        right = max(0, dfs(node.right))

        # Path through current node
        current_path_sum = node.val + left + right
        max_sum = max(max_sum, current_path_sum)

        # Return max contribution to parent
        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;

        // Get max contribution from left and right (ignore negative)
        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));

        // Path through current node
        int currentPathSum = node.val + left + right;
        maxSum = Math.max(maxSum, currentPathSum);

        // Return max contribution to parent
        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;

        // Get max contribution from left and right (ignore negative)
        int left = std::max(0, dfs(node->left));
        int right = std::max(0, dfs(node->right));

        // Path through current node
        int currentPathSum = node->val + left + right;
        maxSum = std::max(maxSum, currentPathSum);

        // Return max contribution to parent
        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
        }

        // Get max contribution from left and right (ignore negative)
        left := max(0, dfs(node.Left))
        right := max(0, dfs(node.Right))

        // Path through current node
        currentPathSum := node.Val + left + right
        if currentPathSum > maxSum {
            maxSum = currentPathSum
        }

        // Return max contribution to parent
        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?

    # Get max contribution from left and right (ignore negative)
    left = [0, dfs.call(node.left)].max
    right = [0, dfs.call(node.right)].max

    # Path through current node
    current_path_sum = node.val + left + right
    @max_sum = [@max_sum, current_path_sum].max

    # Return max contribution to parent
    node.val + [left, right].max
  }

  dfs.call(root)
  @max_sum
end

9. Serialize and Deserialize Binary Tree

  • Brief: Design an algorithm to serialize a binary tree to a string and deserialize it back.
  • Why this pattern?: Preorder traversal with null markers captures tree structure completely.
  • Key Insight: Use a delimiter to separate values and mark null nodes explicitly.
  flowchart LR
    subgraph Tree["Binary Tree"]
        A((1))
        B((2))
        C((3))
        D((4))
        E((5))

        A --> B
        A --> C
        C --> D
        C --> E
    end

    subgraph Serialized["Serialized String"]
        S1["1,2,null,null,3,4,null,null,5,null,null"]
    end

    Tree -->|serialize| Serialized
    Serialized -->|deserialize| Tree

Complexity: Time

O(N)
| Space
O(N)

function serialize(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(',');
}

function deserialize(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 {
    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);
    }

    private int index;

    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

Recommended Study Order

  1. Start with traversals: Solve problems 1-2 to master inorder and preorder.
  2. Build intuition: Problem 3 (Maximum Depth) and 4 (Same Tree) teach recursive thinking.
  3. Learn BFS: Problem 5 (Level Order) is the foundation for many tree problems.
  4. Apply BST properties: Problem 6 (Validate BST) uses inorder for validation.
  5. Practice variations: Problem 7 (Zigzag) adds complexity to BFS.
  6. Tackle hard problems: Problems 8-9 combine multiple concepts.
Interview Strategy: Start by identifying if the problem needs DFS (path-based, depth-based) or BFS (level-based). Then choose the appropriate traversal order based on when you need to process the node.