Tree Construction

Cartesian Trees

It’s just a binary tree where each node is greater/smaller (based on value or some derived priority) than all nodes in its left subtree and right subtree. And an inorder traversal of the tree gives back the original array. Note that just the first property is not sufficient, you need the second one as well. This needs that once the root is fixed, the array must be split at the root. Just a max can have any arbitrary structure ( like take every 2nd element to left and rest to right though why would you do that ever ).

Contruction in O(n);

Link: https://leetcode.com/problems/maximum-binary-tree

A range max is trivial but that will be O(n log n) atleast. A stack based approach is O(n)

TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    // this is a "classic" problem
    // you move from left to right ( as you want to build as in order )
    // the idea is that in a stack you build the maximum dq
    // this becomes the "right" path ( from root keep on going right, these will be the stack elements )
    // when you get a new element, you start from the rightmost end of the stack to find the element's appropriate position
    // now once you find what node it should be child of, whether it's left or right depends on whether the parent is left
    // or right in the original array
 
    // another way to think of this is
    // for each elem you search for the nearest elem >= it in the prefix, this becomes the parent
    // while getting to it, whatever you pop has cur as it's parent with current
 
    vector<TreeNode*> stk;
 
    for (int num : nums) {
        TreeNode* cur = new TreeNode(num);
 
        // if it's equal the parent is the first of the largest ones
        while (!stk.empty() && stk.back()->val < num) {
            // cur is the rightmost element, any children will go to left
            cur->left = stk.back();  // overwritten so basically I just care about the last assignment here
            stk.pop_back();
        }
 
        // if there is still a node in the stack, then this is larger than cur
        // and then should be the parent of cur
        // stack only has left elements so cur goes to the right
        if (!stk.empty())
            stk.back()->right = cur;
 
        stk.emplace_back(cur);
    }
 
    return stk.front();  // largest elem
}

Binary Search Trees

Problems

BST from Preorder Traversal

Link: https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal

class Solution {
   public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        // preorder -> node left right
        // so the first elem will be the root
        // the remaining array will be split at some point where all values left <= all values right
        int i = 0;
        return build(preorder, i, (int)1e9);
    }
 
    TreeNode* build(auto& preorder, int& i, int bound) {
        if (i >= (int)preorder.size() || preorder[i] > bound) return nullptr;
 
        TreeNode* root = new TreeNode(preorder[i++]);  // first is root for the range
        root->left = build(preorder, i, root->val);    // left is < root
        // this will keep on going left till idx is < the bound for the range
        // and once done we start building rights
        root->right = build(preorder, i, bound);  // right side same bound
        return root;
    }
};