Trees

Given the root of a binary tree, return its maximum depth, which is the number of nodes along the longest path from the root node down to the farthest leaf node.

Use Depth-First Search. The depth of a node is 1 + max(depth(left), depth(right)), and an empty tree has depth 0. Every node is visited exactly once, and the recursion stack grows with the tree height \(H\) (\(O(\log N)\) for a balanced tree, \(O(N)\) for a skewed one).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def maxDepth(root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))
    

Given the roots of two binary trees p and q, write a function to check if they are the same. Two binary trees are the same if they are structurally identical and the nodes have the same values.

Compare the trees recursively. If both nodes are None, they match. If only one is None or the values differ, the trees are different. Otherwise, the trees are the same only if both the left subtrees and the right subtrees are the same. The recursion stops at the first mismatch.

def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
    

Given the root of a binary tree, invert the tree (mirror it), and return its root.

At every node, swap the left and right children, then recursively invert both subtrees. Each node is processed once, and the tree is modified in-place without creating new nodes.

def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root
    

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can appear in the sequence at most once, and the path does not need to pass through the root. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Use post-order DFS. For each node, compute the best gain from its left and right subtrees, ignoring any negative gain by taking max(gain, 0). Two different values matter at each node:

1. The best path that passes through this node (both sides allowed): \(\text{node.val} + \text{left} + \text{right}\). This updates the global answer.
2. The best path extending upward to the parent (only one side allowed): \(\text{node.val} + \max(\text{left}, \text{right})\). This is the value the function returns.

def maxPathSum(root: Optional[TreeNode]) -> int:
    res = root.val

    def dfs(node: Optional[TreeNode]) -> int:
        nonlocal res
        if not node:
            return 0
        left = max(dfs(node.left), 0)
        right = max(dfs(node.right), 0)

        # Path that splits at this node
        res = max(res, node.val + left + right)

        # Path that continues up to the parent
        return node.val + max(left, right)

    dfs(root)
    return res
    

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level).

Use Breadth-First Search with a queue. At the start of each round, the queue holds exactly the nodes of one level, so record len(queue) and process that many nodes, collecting their values and enqueuing their children. Each node enters and leaves the queue once.

from collections import deque

def levelOrder(root: Optional[TreeNode]) -> list[list[int]]:
    res = []
    queue = deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)
    return res
    

Design an algorithm to serialize a binary tree into a string and deserialize that string back into the original tree structure. There is no restriction on the format of the encoding.

Use pre-order traversal and record None children with a marker (N). Because null markers are included, a single pre-order sequence uniquely identifies the tree shape, so no second traversal is needed. To deserialize, read the values from an iterator in the same order: take the next token, return None if it is the marker, otherwise create a node and build its left and right subtrees recursively.

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        res = []

        def dfs(node):
            if not node:
                res.append("N")
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ",".join(res)

    def deserialize(self, data: str) -> Optional[TreeNode]:
        vals = iter(data.split(","))

        def dfs():
            val = next(vals)
            if val == "N":
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        return dfs()
    

Given the roots of two binary trees root and subRoot, return True if there is a subtree of root with the same structure and node values as subRoot, and False otherwise.

The straightforward solution calls the Same Tree check at every node of root, which costs \(O(M \cdot N)\). A faster approach converts each tree into a pre-order string, including null markers, then checks whether one string is a substring of the other. Each value gets a ^ prefix so that a value like 2 cannot match inside 12, and tokens are comma separated. With a linear-time substring search (such as KMP) the whole check is \(O(M + N)\). The traversal here is iterative to avoid deep recursion.

def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def serialize(node: Optional[TreeNode]) -> str:
        res = []
        stack = [node]
        while stack:
            cur = stack.pop()
            if cur is None:
                res.append("#")
            else:
                res.append("^" + str(cur.val))
                stack.append(cur.right)
                stack.append(cur.left)
        return ",".join(res)

    return serialize(subRoot) in serialize(root)
    

Given two integer arrays preorder and inorder, where preorder is the pre-order traversal of a binary tree and inorder is the in-order traversal of the same tree, construct and return the binary tree. All values are unique.

The next unused element in preorder is always the root of the current subtree. Locating that value in inorder splits it into the left subtree (everything before it) and the right subtree (everything after it). Searching the array each time would cost \(O(N^2)\), so store each value's inorder index in a hash map for \(O(1)\) lookups. Build the left subtree before the right one, because pre-order visits the left subtree first. A single shared pointer pre_i advances through preorder, so no array slicing is needed.

def buildTree(preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
    index = {val: i for i, val in enumerate(inorder)}
    pre_i = 0

    def build(left: int, right: int) -> Optional[TreeNode]:
        nonlocal pre_i
        if left > right:
            return None
        root = TreeNode(preorder[pre_i])
        pre_i += 1
        mid = index[root.val]
        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)
        return root

    return build(0, len(inorder) - 1)
    

Given the root of a binary tree, determine if it is a valid binary search tree (BST): the left subtree of a node contains only keys less than the node's key, the right subtree contains only keys greater than the node's key, and both subtrees are also BSTs.

Comparing a node only with its direct children is not enough, since a node must respect all of its ancestors. Instead, pass down a valid range (low, high). Every node must satisfy \(\text{low} < \text{val} < \text{high}\). Going left tightens the upper bound to the current value, and going right tightens the lower bound.

def isValidBST(root: Optional[TreeNode]) -> bool:
    def valid(node, low, high):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return valid(node.left, low, node.val) and valid(node.right, node.val, high)

    return valid(root, float('-inf'), float('inf'))
    

Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed) of all the values of the nodes in the tree.

An in-order traversal of a BST visits values in sorted order. Run the traversal iteratively with an explicit stack and stop as soon as the k-th node is popped, instead of collecting all \(N\) values first. Going down to the leftmost node costs \(O(H)\), and then only k nodes are processed.

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    curr = root
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
        curr = curr.right
    

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes p and q. The LCA is the lowest node that has both p and q as descendants (a node can be a descendant of itself).

Use the BST ordering property. Starting at the root, if both p and q are smaller than the current node, the LCA must be in the left subtree. If both are larger, it is in the right subtree. Otherwise, p and q are on different sides of the current node (or one of them equals it), which makes the current node the LCA. This iterative walk follows a single root-to-node path.

def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    curr = root
    while curr:
        if p.val < curr.val and q.val < curr.val:
            curr = curr.left
        elif p.val > curr.val and q.val > curr.val:
            curr = curr.right
        else:
            return curr
    

Implement a Trie with insert(word), search(word) (returns True if the word is in the trie) and startsWith(prefix) (returns True if any inserted word has the given prefix).

Each trie node holds a dictionary mapping a character to its child node, plus an is_end flag marking the end of a complete word. All operations walk one node per character, so they cost \(O(L)\) where \(L\) is the length of the word or prefix. search and startsWith share the same traversal, and the only difference is that search also requires is_end to be set.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix: str) -> Optional[TrieNode]:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None
    

Design a data structure that supports adding new words and finding if a string matches any previously added word. search(word) may contain dots ., where a dot can match any letter.

Store the words in a Trie, exactly as in the previous problem. For search, use DFS with the current position in the word. A normal letter follows the single matching child. A dot branches into every child of the current node, and the search succeeds if any branch matches the rest of the word. The wildcard branching only blows up when the word has many dots, which is the worst case.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(i: int, node: TrieNode) -> bool:
            for j in range(i, len(word)):
                ch = word[j]
                if ch == '.':
                    # Try every child for the wildcard
                    for child in node.children.values():
                        if dfs(j + 1, child):
                            return True
                    return False
                if ch not in node.children:
                    return False
                node = node.children[ch]
            return node.is_end

        return dfs(0, self.root)
    

Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells (horizontally or vertically), and the same cell may not be used more than once in a word.

Running Word Search I once per word repeats a lot of work. Instead, insert all words into a single Trie and run one backtracking DFS from every cell, moving only into neighbors that exist as children in the current trie node. This prunes every path that is not a prefix of some word. Three optimizations make it fast: store the complete word at its end node so no string has to be rebuilt, set node.word = None after finding it to avoid duplicate results, and delete exhausted trie branches so later searches skip dead prefixes. Here \(L\) is the maximum word length.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # full word stored at its end node

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, TrieNode())
        node.word = w

    rows, cols = len(board), len(board[0])
    res = []

    def dfs(r: int, c: int, parent: TrieNode) -> None:
        ch = board[r][c]
        node = parent.children[ch]

        if node.word:
            res.append(node.word)
            node.word = None  # avoid duplicates

        board[r][c] = '#'  # mark visited
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in node.children:
                dfs(nr, nc, node)
        board[r][c] = ch  # backtrack

        # Prune exhausted branches
        if not node.children:
            del parent.children[ch]

    for r in range(rows):
        for c in range(cols):
            if board[r][c] in root.children:
                dfs(r, c, root)
    return res