Constructing Maximum Binary Tree (Problem 654)

This problem requires building a binary tree from an integer array where the maximum element becomes the root, and the process repeats recursively for left and right subarrays. The solution involves identifying the peak value within a specified range and recursively constructing subtrees for the remainign elements.

Key approach: Use index boundaries instead of creating subarrays to optimize space complexity. The algorithm processes the array segment between left and right indices, finds the maximum element's position, creates a node, and recursively builds left and right subtrees.

class Solution {
private:
    TreeNode* buildTree(vector<int>& arr, int start, int end) {
        if (start > end) return nullptr;
        
        int maxValue = arr[start];
        int maxIndex = start;
        for (int i = start + 1; i <= end; i++) {
            if (arr[i] > maxValue) {
                maxValue = arr[i];
                maxIndex = i;
            }
        }
        
        TreeNode* node = new TreeNode(maxValue);
        node->left = buildTree(arr, start, maxIndex - 1);
        node->right = buildTree(arr, maxIndex + 1, end);
        return node;
    }
    
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return buildTree(nums, 0, nums.size() - 1);
    }
};
</int></int>

Merging Two Binary Trees (Problem 617)

When merging two binary trees, we need to combine corresponding nodes. If nodes exist at the same position in both trees, we sum their values. If a node exists in only one tree, we preserve it as-is. The solution can be implemented recursively, modifying one of the original trees to save space.

Recursive strategy: Start from roots, check for null cases, combine values, and recursively process children. The operation can be performed in-place by modifying the first tree.

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1) return t2;
        if (!t2) return t1;
        
        TreeNode* merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }
};

// Space-optimized version
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1) return t2;
        if (!t2) return t1;
        
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

Searching in Binary Search Tree (Problem 700)

BST properties enable efficient searching: left subtree values are less than root, right subtree values are greater. This eliminates the need for backtracking, allowing direct path traversal too the target value.

Both recursive and iterative approaches work well. The iterative version is often preferred for its constant space usage.

// Recursive solution
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int target) {
        if (!root) return nullptr;
        if (root->val == target) return root;
        
        return target < root->val ? 
               searchBST(root->left, target) : 
               searchBST(root->right, target);
    }
};

// Iterative solution
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int target) {
        while (root) {
            if (root->val == target) return root;
            root = target < root->val ? root->left : root->right;
        }
        return nullptr;
    }
};

Validating Binary Search Tree (Problem 98)

A BST must maintain ordering: all left subtree nodes must be less than root, all right subtree nodes must be greater. We can validaet this using three main approaches:

1. Inorder traversal with array storage - traverse inorder and check if resulting array is strictly increasing.

class Solution {
private:
    vector<int> values;
    
    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        values.push_back(node->val);
        inorder(node->right);
    }
    
public:
    bool isValidBST(TreeNode* root) {
        inorder(root);
        for (int i = 1; i < values.size(); i++) {
            if (values[i] <= values[i-1]) return false;
        }
        return true;
    }
};
</int>

2. Inorder traversal with previous node tracking - maintain previous node pointer during traversal.

class Solution {
private:
    TreeNode* prev = nullptr;
    
public:
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        
        if (!isValidBST(root->left)) return false;
        if (prev && prev->val >= root->val) return false;
        prev = root;
        return isValidBST(root->right);
    }
};

3. Range validation with recursion - maintain valid range (min, max) for each node.

class Solution {
private:
    bool validate(TreeNode* node, long minVal, long maxVal) {
        if (!node) return true;
        if (node->val <= minVal || node->val >= maxVal) return false;
        return validate(node->left, minVal, node->val) && 
               validate(node->right, node->val, maxVal);
    }
    
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, LONG_MIN, LONG_MAX);
    }
};