Tree DFS Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

// Recursive DFS: the three orders differ only in WHERE you handle the node.
void dfs(TreeNode* node, vector<int>& out) {
    if (!node) return;
    // preorder:  out.push_back(node->val);   (node before its children)
    dfs(node->left, out);
    out.push_back(node->val);                 // inorder: between the two children
    dfs(node->right, out);
    // postorder: out.push_back(node->val);  (node after both children)
}

// Iterative inorder with your own stack: go left as far as possible, then visit, then go right.
vector<int> inorderIterative(TreeNode* root) {
    vector<int> out;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }   // everything on the way down waits its turn
        cur = st.top(); st.pop();
        out.push_back(cur->val);                         // its whole left side is already done
        cur = cur->right;
    }
    return out;
}

// Two trees at once: compare the pair, then recurse on matching pairs of children.
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p || !q) return p == q;                         // both null → same; one null → different
    return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

// Top-down: carry the path's state as a parameter; check it at the leaves.
// Here: every root-to-leaf path whose sum is target (Path Sum II).
void walk(TreeNode* node, int remaining, vector<int>& path, vector<vector<int>>& out) {
    if (!node) return;
    path.push_back(node->val);                           // enter: add this node to the path
    remaining -= node->val;
    if (!node->left && !node->right) {                   // a leaf: the path is complete
        if (remaining == 0) out.push_back(path);
    } else {
        walk(node->left, remaining, path, out);
        walk(node->right, remaining, path, out);
    }
    path.pop_back();                                     // leave: undo, so the parent's path is clean
}

vector<vector<int>> pathSum(TreeNode* root, int target) {
    vector<vector<int>> out;
    vector<int> path;
    walk(root, target, path, out);
    return out;
}

// Bottom-up: each call returns a summary of its subtree; the global answer is
// updated while combining the two children. Here: diameter (longest path, in edges).
int best = 0;

int height(TreeNode* node) {                             // returns: nodes on the longest downward path
    if (!node) return 0;
    int lh = height(node->left);
    int rh = height(node->right);
    best = max(best, lh + rh);                           // the longest path that bends at this node
    return 1 + max(lh, rh);                              // a parent can only extend ONE side
}

int diameterOfBinaryTree(TreeNode* root) {
    best = 0;
    height(root);
    return best;
}

// BST: every node must fit inside the (low, high) range set by its ancestors.
// long long bounds so a node equal to INT_MIN or INT_MAX still fits.
bool valid(TreeNode* node, long long low, long long high) {
    if (!node) return true;
    if (node->val <= low || node->val >= high) return false;
    return valid(node->left, low, node->val)             // left side: everything below node->val
        && valid(node->right, node->val, high);          // right side: everything above node->val
}

bool isValidBST(TreeNode* root) { return valid(root, LLONG_MIN, LLONG_MAX); }

// Searching only needs one side: the comparison tells you where the value must be.
TreeNode* searchBST(TreeNode* root, int target) {
    while (root && root->val != target)
        root = target < root->val ? root->left : root->right;
    return root;
}

// Lowest common ancestor in a plain binary tree, in one post-order pass.
// Each call returns p or q if it found one below (or is one), else nullptr.
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;                      // p and q split here: this is the LCA
    return left ? left : right;                          // pass up whichever side found something
}

// Build from preorder + inorder: preorder gives the next root, its position
// in inorder splits the left and right subtrees.
TreeNode* build(vector<int>& pre, int& next, int lo, int hi, unordered_map<int, int>& pos) {
    if (lo > hi) return nullptr;                         // empty inorder range → no subtree
    int val = pre[next++];
    TreeNode* node = new TreeNode(val);
    int mid = pos[val];
    node->left = build(pre, next, lo, mid - 1, pos);     // left first: preorder is root, left, right
    node->right = build(pre, next, mid + 1, hi, pos);
    return node;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> pos;                         // value → index in inorder (values are unique)
    for (int i = 0; i < (int)inorder.size(); i++) pos[inorder[i]] = i;
    int next = 0;
    return build(preorder, next, 0, (int)inorder.size() - 1, pos);
}