Trees

Reach for it when

• Binary tree / BST input
• Depth, diameter, path sums, balance, ancestors
• Level-by-level output (BFS)

Core idea

Most tree problems are a post-order DFS: ask each child for a summary, combine the two summaries at the node, and return a summary to the parent. If the answer may not pass through the root, update a global best while returning a different value upward. BSTs add an ordering invariant that in-order traversal visits in sorted order.

Template · O(n) time, O(h) recursion stack

def diameter(root):
    best = 0
    def depth(node):
        nonlocal best
        if not node:
            return 0
        l, r = depth(node.left), depth(node.right)
        best = max(best, l + r)       # path bending at node
        return 1 + max(l, r)          # path continuing upward
    depth(root)
    return best

int diameter(TreeNode* root) {
    int best = 0;
    function<int(TreeNode*)> depth = [&](TreeNode* node) {
        if (!node) return 0;
        int l = depth(node->left), r = depth(node->right);
        best = max(best, l + r);      // path bending at node
        return 1 + max(l, r);         // path continuing upward
    };
    depth(root);
    return best;
}

Common pitfalls

• Confusing what you return upward with what you record globally
• BST validation needs (low, high) bounds, not just parent comparisons
• Deep skewed trees can hit the recursion limit: use an explicit stack

Practice · 0 / 18 done

• Balanced Binary TreeEasy
• Diameter of Binary TreeEasy
• Invert Binary TreeEasy
• Maximum Depth of Binary TreeEasy
• Same TreeEasy
• Subtree of Another TreeEasy
• Amount of Time for Binary Tree to Be InfectedMedium
• Binary Tree Level Order TraversalMedium
• Binary Tree Right Side ViewMedium
• Construct Binary Tree From Preorder And Inorder TraversalMedium
• Count Good Nodes In Binary TreeMedium
• House Robber IIIMedium
• Kth Smallest Element In a BstMedium
• Lowest Common Ancestor of a Binary Search TreeMedium
• Lowest Common Ancestor of a Binary TreeMedium
• Validate Binary Search TreeMedium
• Binary Tree Maximum Path SumHard
• Serialize And Deserialize Binary TreeHard