Trees | DSA Prep

Core Concepts

Most tree problems are solved using traversal algorithms. You must be comfortable with recursion.

Depth First Search (DFS): Pre-order, In-order, and Post-order traversals using recursion or a stack.
Breadth First Search (BFS): Level-order traversal using a queue.
Binary Search Trees (BST): Trees where the left child is smaller and the right child is larger than the parent.

graph TD A((4)) --> B((2)) A --> C((7)) B --> D((1)) B --> E((3)) C --> F((6)) C --> G((9)) classDef node fill:#e2e8f0,stroke:#94a3b8,color:#1e293b,font-weight:bold; class A,B,C,D,E,F,G node;

Cheatsheet Formulas

DFS (Recursive): if not node: return. Process node (Pre), recurse left, process node (In), recurse right, process node (Post).
BFS (Level Order): queue = [root]. while queue: size = len(queue). Loop size times: pop, process, add children.
BST Property: Left child strictly less than parent, right child strictly greater than parent. In-order traversal of BST yields sorted array!

Classic Problem: Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root. (The famous Homebrew problem).

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        
        return root;
    }
}

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

Classic Problem: Maximum Depth of Binary Tree

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

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

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