Constructing a Maximum Binary Tree

Given a unique integer array nums, construct a maximum binary tree following these recursive steps:

1. Create a root node with the maximum value in the array.
2. Recursively build the left subtree from the elements before the maximum value.
3. Recursive build the right subtree from the elements after the maximum value.

The implementation uses a recursive approach with preorder traversal logic:

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(std::vector<int>& nums) {
        if (nums.empty()) return nullptr;
        
        // Find maximum value and its index
        int maxIndex = 0;
        int maxValue = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        
        TreeNode* node = new TreeNode(maxValue);
        
        // Split array and recurse
        std::vector<int> leftVec(nums.begin(), nums.begin() + maxIndex);
        std::vector<int> rightVec(nums.begin() + maxIndex + 1, nums.end());
        
        node->left = constructMaximumBinaryTree(leftVec);
        node->right = constructMaximumBinaryTree(rightVec);
        
        return node;
    }
};

Merging Two Binary Trees

Combine two binary trees by overlapping nodes and summing their values. When nodes don't overlap, use the non-null node as-is.

The implementation uses a recursive preorder traversal approach:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1) return t2;
        if (!t2) return t1;
        
        // Merge current nodes
        t1->val += t2->val;
        
        // Recursively merge children
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        
        return t1;
    }
};

Searching in a Binary Search Tree (BST)

Locate a specific value in a BST by leveraging its ordered structure:

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root || root->val == val) return root;
        
        if (root->val > val) {
            return searchBST(root->left, val);
        } else {
            return searchBST(root->right, val);
        }
    }
};

Validating a Binary Search Tree

Verify if a binary tree is a valid BST by checking in-order traversal produces an increasing sequence:

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