Maximum Binary Tree Construction

Given an array of integers, construct a binary tree where each parent node contains the maximum value of its respective subarray. The maximum element becomes the root, with the left subtree built from elements to the left of the maximum, and the right subtree from elements to the right.

Implementation utilizes a recursive helper function that operates on index ranges rather than copying subarrays, optimizing space complexity:

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

Merging Binary Trees

When combining two binary trees, overlay they structures by summing overlapping node values. The merge operation creates a unified tree where both inputs contribute to the final structure. If one tree lacks a node at a specific posision, the corresponding node from the other tree is adopted directly.

The algorithm employs pre-order traversal, procesing the current node before recursing into children:

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* first, TreeNode* second) {
        if (!first) return second;
        if (!second) return first;
        
        first->val += second->val;
        first->left = mergeTrees(first->left, second->left);
        first->right = mergeTrees(first->right, second->right);
        return first;
    }
};

Searching in a Binary Search Tree

Leveraging the BST property where left descendants are smaller and right descendants are larger than their parent, we can locate a target value efficiently without examining every node.

Recursive approach:

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

Iterative implementation eliminates call stack overhead:

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int target) {
        while (root && root->val != target) {
            root = target < root->val ? root->left : root->right;
        }
        return root;
    }
};

Validating Binary Search Tree Properties

A valid BST requires that every node's left subtree contains only smaller values and right subtree only larger values. Two primary approaches exist:

Inorder Traversal Validation: Collect values during inorder traversal (left-root-right) and verify the resulting sequence is strictly increasing.

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

Continuous Tracking: During traversal, maintain a reference to the previously visited node to ensure each current value exceeds its predecessor.

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