Finding the Bottom-Left Node Value

Given the root of a binary tree, return the value of the leftmost node at the deepest level.

Breadth-First Search (Iterative)

A level-order traversal naturally visits nodes layer by layer. The first node encountered in the final level is the answer.

#include <queue>

int findBottomLeftValue(TreeNode* root) {
    std::queue<TreeNode*> q;
    if (!root) return 0;
    q.push(root);
    int result = 0;

    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* current = q.front();
            q.pop();
            if (i == 0) result = current->val;
            if (current->left) q.push(current->left);
            if (current->right) q.push(current->right);
        }
    }
    return result;
}

Depth-First Search (Recursive with State Tracking)

Track the current depth and maintain the maximum depth seen so far. Udpate the result only when descending deeper than any previous path.

int findBottomLeftValue(TreeNode* root) {
    int maxDepth = -1;
    int leftmost = 0;

    std::function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int depth) {
        if (!node) return;
        if (depth > maxDepth) {
            maxDepth = depth;
            leftmost = node->val;
        }
        dfs(node->left, depth + 1);
        dfs(node->right, depth + 1);
    };

    dfs(root, 0);
    return leftmost;
}

Path Sum Detection and Enumeration

112. Path Sum (Existence Check)

Determine whether any root-to-leaf path sums to a given target.

Recursive Approach with Early Termination

Subtract each node’s value from the remaining sum as we descend. Return true immediate upon reaching a leaf with zero remaining sum.

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    if (!root->left && !root->right) {
        return targetSum == root->val;
    }
    return hasPathSum(root->left, targetSum - root->val) ||
           hasPathSum(root->right, targetSum - root->val);
}

113. Path Sum II (All Valid Paths)

Collect all root-to-leaf paths whose values sum to the target.

Backtracking with Mutable Path State

Maintain a path vector that grows on descent and shrinks on ascent. Append full paths only at qualifying leaves.

std::vector<std::vector<int>> pathSum(TreeNode* root, int targetSum) {
    std::vector<std::vector<int>> results;
    std::vector<int> currentPath;

    std::function<void(TreeNode*, int)> backtrack = [&](TreeNode* node, int remaining) {
        if (!node) return;
        currentPath.push_back(node->val);
        remaining -= node->val;

        if (!node->left && !node->right && remaining == 0) {
            results.push_back(currentPath);
        } else {
            backtrack(node->left, remaining);
            backtrack(node->right, remaining);
        }
        currentPath.pop_back(); // backtrack
    };

    backtrack(root, targetSum);
    return results;
}

Reconstructing Binary Trees from Traversal Sequences

106. Construct from Inorder and Postorder

The last element in postorder is always the root. Locate it in inorder to split left/right subtrees, then recursively reconstruct.

Efficient Index-Based Recursion

Avoid copying subarrays; instead pass inclusive start and exclusive end indices.

TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
    std::function<TreeNode*(int, int, int, int)> helper =
        [&](int inStart, int inEnd, int postStart, int postEnd) -> TreeNode* {
            if (inStart >= inEnd || postStart >= postEnd) return nullptr;

            int rootVal = postorder[postEnd - 1];
            TreeNode* root = new TreeNode(rootVal);

            int rootIdx = inStart;
            while (rootIdx < inEnd && inorder[rootIdx] != rootVal) ++rootIdx;

            int leftSize = rootIdx - inStart;
            root->left = helper(inStart, rootIdx, postStart, postStart + leftSize);
            root->right = helper(rootIdx + 1, inEnd, postStart + leftSize, postEnd - 1);
            return root;
        };

    return helper(0, inorder.size(), 0, postorder.size());
}

105. Construct from Preorder and Inorder

The first element in preorder is the root. Partition inorder around it and map corresponding segments in preorder.

Index-Based Recursive Construction

Same principal as above, but adjust index offsets for preorder’s root-first ordering.

TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
    std::function<TreeNode*(int, int, int, int)> helper =
        [&](int inStart, int inEnd, int preStart, int preEnd) -> TreeNode* {
            if (inStart >= inEnd || preStart >= preEnd) return nullptr;

            int rootVal = preorder[preStart];
            TreeNode* root = new TreeNode(rootVal);

            int rootIdx = inStart;
            while (rootIdx < inEnd && inorder[rootIdx] != rootVal) ++rootIdx;

            int leftSize = rootIdx - inStart;
            root->left = helper(inStart, rootIdx, preStart + 1, preStart + 1 + leftSize);
            root->right = helper(rootIdx + 1, inEnd, preStart + 1 + leftSize, preEnd);
            return root;
        };

    return helper(0, inorder.size(), 0, preorder.size());
}