Constructing a Maximum Binary Tree

For constructing binary tree problems, pre-order traversal is always used because it visits the root first, allowing us to build left and right subtrees after initializing the root.

The core idea is to repeated find the maximum value in the current array range as the subtree root, then recursively construct left and right subtrees from the left and right segments of this maximum value. To optimize efficiency, we avoid creating new subarrays by directly manipulating indices in a left-closed right-open range [left, right).

class Solution {
private:
    TreeNode* buildTree(vector<int>& data, int left, int right) {
        if (left >= right) return nullptr;

        int maxPos = left;
        for (int i = left + 1; i < right; ++i) {
            if (data[i] > data[maxPos]) maxPos = i;
        }

        TreeNode* root = new TreeNode(data[maxPos]);
        root->left = buildTree(data, left, maxPos);
        root->right = buildTree(data, maxPos + 1, right);
        return root;
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& data) {
        return buildTree(data, 0, data.size());
    }
};

Merging Two Binary Trees

Merging two binary trees uses a synchronous traversal approach, and pre-order traversal is the most intuitive choice. The key is to handle null nodes appropriately: if one tree’s node is null, the merged subtree is directly the corresponding node from the other tree. We can either modify one of the original trees or create a new tree.

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1) return t2;
        if (!t2) return t1;

        TreeNode* newRoot = new TreeNode(t1->val + t2->val);
        newRoot->left = mergeTrees(t1->left, t2->left);
        newRoot->right = mergeTrees(t1->right, t2->right);
        return newRoot;
    }
};

Searching in a Binary Search Tree (BST)

BST has the property that left subtree nodes are all smaller than the root, and right subtree nodes are all larger. This property eliminates the need for full traversal; we can search in the left or right subtree based on value comparison.

Recursive Solution

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

        if (target < root->val) {
            return searchBST(root->left, target);
        } else {
            return 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 a Binary Search Tree (BST)

The most crucial property of BST is that its in-order traversal produces a strictly increasing sequence. We can validate BST by either collecting all node values during in-order traversal and checking if they are strictly increasing, or by checking the order directly during traversal.

In-order Traversal with Array Check

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

Direct In-order Traversal Check

class Solution {
private:
    TreeNode* prev = nullptr;
    bool validate(TreeNode* root) {
        if (!root) return true;

        if (!validate(root->left)) return false;

        if (prev && prev->val >= root->val) return false;
        prev = root;

        return validate(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        prev = nullptr;
        return validate(root);
    }
};

Iterative In-order Traversal Check

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* curr = root;
        TreeNode* prev = nullptr;

        while (curr || !st.empty()) {
            while (curr) {
                st.push(curr);
                curr = curr->left;
            }

            curr = st.top();
            st.pop();

            if (prev && prev->val >= curr->val) return false;
            prev = curr;

            curr = curr->right;
        }

        return true;
    }
};

Range-Based Recursive Check

A more elegant approach checks the valid range of each node's value during traversal, ensuring all left subtree nodes are within [min, current value) and alright subtree nodes are within (current value, max].

class Solution {
private:
    bool isValidRange(TreeNode* node, TreeNode* lowerBound, TreeNode* upperBound) {
        if (!node) return true;

        if (lowerBound && lowerBound->val >= node->val) return false;
        if (upperBound && upperBound->val <= node->val) return false;

        return isValidRange(node->left, lowerBound, node) && isValidRange(node->right, node, upperBound);
    }
public:
    bool isValidBST(TreeNode* root) {
        return isValidRange(root, nullptr, nullptr);
    }
};