Binary Trees

// For a perfect binary tree of height h:
int nodes_at_level_h  = pow(2, h);        // Nodes at last level
int total_nodes       = pow(2, h+1) - 1;  // Total nodes
int total_leaves      = pow(2, h);        // Leaf nodes
 
// For a complete binary tree with n nodes:
int height = floor(log2(n));              // Height = floor(log₂n)
 
// For any binary tree with n nodes:
// Minimum height (balanced): floor(log₂n)
// Maximum height (skewed):   n - 1

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode()              : val(0),   left(nullptr), right(nullptr) {}
    TreeNode(int x)         : val(x),   left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {}
};
 
// Build manually
TreeNode* root = new TreeNode(1);
root->left     = new TreeNode(2);
root->right    = new TreeNode(3);
root->left->left  = new TreeNode(4);
root->left->right = new TreeNode(5);
 
// Build from level-order array (LeetCode format: -1 or INT_MIN = null)
TreeNode* buildFromArray(vector<int>& arr) {
    if (arr.empty() || arr[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(arr[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < (int)arr.size()) {
        TreeNode* node = q.front(); q.pop();
        if (i < (int)arr.size() && arr[i] != -1) {
            node->left = new TreeNode(arr[i]);
            q.push(node->left);
        }
        i++;
        if (i < (int)arr.size() && arr[i] != -1) {
            node->right = new TreeNode(arr[i]);
            q.push(node->right);
        }
        i++;
    }
    return root;
}

class TreeArray {
    vector<int> tree;
public:
    TreeArray(int n) : tree(n, -1) {}
 
    void setVal(int i, int val)  { tree[i] = val; }
    int  left(int i)  { return 2*i + 1; }
    int  right(int i) { return 2*i + 2; }
    int  parent(int i){ return (i - 1) / 2; }
    bool exists(int i){ return i < (int)tree.size() && tree[i] != -1; }
};

// Inorder: Left → Root → Right
// Key property: gives SORTED output for a valid BST
void inorder(TreeNode* node, vector<int>& result) {
    if (!node) return;
    inorder(node->left, result);
    result.push_back(node->val);   // Visit root between children
    inorder(node->right, result);
}
 
// Preorder: Root → Left → Right
// Key property: root always comes first; used to copy/serialize a tree
void preorder(TreeNode* node, vector<int>& result) {
    if (!node) return;
    result.push_back(node->val);   // Visit root first
    preorder(node->left, result);
    preorder(node->right, result);
}
 
// Postorder: Left → Right → Root
// Key property: root always comes last; used when a node needs its children
//               processed before itself (delete tree, evaluate expressions)
void postorder(TreeNode* node, vector<int>& result) {
    if (!node) return;
    postorder(node->left, result);
    postorder(node->right, result);
    result.push_back(node->val);   // Visit root last
}
 
// Level-order: BFS layer by layer
vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        result.emplace_back();
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            result.back().push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return result;
}

vector<int> inorderIterative(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* curr = root;
 
    while (curr || !st.empty()) {
        // Go as far LEFT as possible, pushing nodes along the way
        while (curr) { st.push(curr); curr = curr->left; }
        // Pop, visit, then go RIGHT
        curr = st.top(); st.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }
    return result;
}
// Time: O(n), Space: O(h)

vector<int> preorderIterative(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        result.push_back(node->val);           // Visit root
        if (node->right) st.push(node->right); // Right first (LIFO → left processed first)
        if (node->left)  st.push(node->left);
    }
    return result;
}

vector<int> postorderIterative(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        result.push_back(node->val);
        if (node->left)  st.push(node->left);  // Left first (reversed in final result)
        if (node->right) st.push(node->right);
    }
    reverse(result.begin(), result.end());
    return result;
}
// Trick: Root→Right→Left reversed = Left→Right→Root (postorder)

int height(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}
// Time: O(n), Space: O(h) — visits every node once
// Returns 0 for null, 1 for a single node (number of nodes, not edges)
// For edge-based height: return -1 for null, then add 1

int diameterOfBinaryTree(TreeNode* root) {
    int maxDiameter = 0;
 
    function<int(TreeNode*)> height = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int leftH  = height(node->left);
        int rightH = height(node->right);
        // Update global diameter: path through this node
        maxDiameter = max(maxDiameter, leftH + rightH);
        return 1 + max(leftH, rightH);   // Return height to parent
    };
 
    height(root);
    return maxDiameter;
}
// Time: O(n), Space: O(h)
// Critical insight: returns height to the parent but updates maxDiameter internally.
// This "dual-purpose" return is a key tree pattern.
 
/*
  Tree:    1
          / \
         2   3
        / \
       4   5
 
  height(4) = 1, height(5) = 1
  At node 2: leftH=1, rightH=1. Diameter candidate = 2. return 2.
  height(3) = 1
  At node 1: leftH=2, rightH=1. Diameter candidate = 3. return 3.
  maxDiameter = 3 (path: 4→2→1→3 or 5→2→1→3)
*/

bool isBalanced(TreeNode* root) {
    function<int(TreeNode*)> checkHeight = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int leftH = checkHeight(node->left);
        if (leftH == -1) return -1;    // Propagate unbalanced
        int rightH = checkHeight(node->right);
        if (rightH == -1) return -1;   // Propagate unbalanced
        if (abs(leftH - rightH) > 1) return -1;  // This node unbalanced
        return 1 + max(leftH, rightH);
    };
    return checkHeight(root) != -1;
}
// Time: O(n), Space: O(h)
// The -1 sentinel short-circuits: once any subtree is unbalanced,
// no further computation happens — elegant early termination.

// Minimum depth = shortest path from root to any LEAF
// Warning: A node with only one child is NOT a leaf — must go to both children
int minDepth(TreeNode* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return 1;   // Leaf node
 
    // If only one child exists, must go through that child
    if (!root->left)  return 1 + minDepth(root->right);
    if (!root->right) return 1 + minDepth(root->left);
 
    return 1 + min(minDepth(root->left), minDepth(root->right));
}
// Time: O(n), Space: O(h)

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root)      return nullptr;   // Reached null — neither p nor q here
    if (root == p || root == q) return root;   // Found p or q — return it
 
    TreeNode* left  = lowestCommonAncestor(root->left,  p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
 
    if (left && right) return root;   // p in one subtree, q in other → root is LCA
    return left ? left : right;       // Both in same subtree — propagate the found one
}
// Time: O(n), Space: O(h)
 
/*
  Tree:    3
          / \
         5   1
        / \ / \
       6  2 0  8
         / \
        7   4
  LCA(5, 1) → 3 (left=5, right=1, both non-null → return root=3)
  LCA(5, 4) → 5 (left=5 found at node 5, right=null → return 5)
*/

// In a BST, LCA is the split point:
// If both p and q < root → LCA in left subtree
// If both p and q > root → LCA in right subtree
// Otherwise → root is LCA (one on each side, or one IS root)
TreeNode* lowestCommonAncestorBST(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root) {
        if (p->val < root->val && q->val < root->val) root = root->left;
        else if (p->val > root->val && q->val > root->val) root = root->right;
        else return root;   // Split point — this is the LCA
    }
    return nullptr;
}
// Time: O(h) = O(log n) for balanced BST, O(n) worst case
// Space: O(1) — iterative!

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false;
    if (!root->left && !root->right) return root->val == targetSum;  // Leaf check
    return hasPathSum(root->left,  targetSum - root->val) ||
           hasPathSum(root->right, targetSum - root->val);
}
// Time: O(n), Space: O(h)

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>> result;
    vector<int> path;
 
    function<void(TreeNode*, int)> dfs = [&](TreeNode* node, int remaining) {
        if (!node) return;
        path.push_back(node->val);
        remaining -= node->val;
 
        if (!node->left && !node->right && remaining == 0) {
            result.push_back(path);   // Found valid path
        } else {
            dfs(node->left,  remaining);
            dfs(node->right, remaining);
        }
        path.pop_back();   // Backtrack
    };
 
    dfs(root, targetSum);
    return result;
}
// Time: O(n²) worst case — copying path for each leaf
// Space: O(h) for recursion stack

int maxPathSum(TreeNode* root) {
    int globalMax = INT_MIN;
 
    function<int(TreeNode*)> maxGain = [&](TreeNode* node) -> int {
        if (!node) return 0;
 
        // Max gain from each subtree; ignore negative contributions
        int leftGain  = max(0, maxGain(node->left));
        int rightGain = max(0, maxGain(node->right));
 
        // Update global max: path through this node (can use BOTH subtrees)
        globalMax = max(globalMax, node->val + leftGain + rightGain);
 
        // Return max gain this node can contribute to its PARENT
        // (parent can only extend one direction — choose the better subtree)
        return node->val + max(leftGain, rightGain);
    };
 
    maxGain(root);
    return globalMax;
}
// Time: O(n), Space: O(h)
 
/*
  Tree:    -10
           /  \
          9    20
              /  \
             15    7
 
  At 15: leftGain=0, rightGain=0. globalMax=15. return 15.
  At 7:  leftGain=0, rightGain=0. globalMax=15. return 7.
  At 20: leftGain=15, rightGain=7. globalMax=max(15, 20+15+7)=42. return 20+15=35.
  At -10: leftGain=max(0,9)=9, rightGain=max(0,35)=35.
          globalMax=max(42, -10+9+35)=max(42,34)=42. return -10+35=25.
  Answer: 42 (path: 15→20→7)
*/

int pathSum(TreeNode* root, long long targetSum) {
    unordered_map<long long, int> prefixCount;
    prefixCount[0] = 1;   // Empty path (before any node)
    int count = 0;
 
    function<void(TreeNode*, long long)> dfs = [&](TreeNode* node, long long currSum) {
        if (!node) return;
        currSum += node->val;
 
        // Count paths ending at this node with sum = targetSum
        count += prefixCount[currSum - targetSum];
 
        // Add current prefix sum to map
        prefixCount[currSum]++;
 
        dfs(node->left,  currSum);
        dfs(node->right, currSum);
 
        // Backtrack: remove current prefix sum (leaving this subtree)
        prefixCount[currSum]--;
    };
 
    dfs(root, 0);
    return count;
}
// Time: O(n), Space: O(n) — hash map + recursion stack
// Key: prefixCount[currSum - target] counts paths that started earlier
//      and ended here with the exact target sum.

vector<int> leftView(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            if (i == 0) result.push_back(node->val);  // First in level
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return result;
}

vector<int> rightSideView(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            if (i == sz - 1) result.push_back(node->val);  // Last in level
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return result;
}
 
// Recursive version using DFS (visit right before left):
void rightViewDFS(TreeNode* node, int depth, vector<int>& result) {
    if (!node) return;
    if (depth == (int)result.size()) result.push_back(node->val);  // First visit at this depth
    rightViewDFS(node->right, depth+1, result);  // Right first
    rightViewDFS(node->left,  depth+1, result);
}

vector<int> topView(TreeNode* root) {
    if (!root) return {};
    map<int, int> hdToVal;      // HD → value of topmost (first-seen) node
    queue<pair<TreeNode*, int>> q;  // {node, horizontal distance}
    q.push({root, 0});
 
    while (!q.empty()) {
        auto [node, hd] = q.front(); q.pop();
        if (!hdToVal.count(hd))     // Only record first (topmost) node at each HD
            hdToVal[hd] = node->val;
        if (node->left)  q.push({node->left,  hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    vector<int> result;
    for (auto& [hd, val] : hdToVal) result.push_back(val);
    return result;  // map keeps HDs sorted
}
// Time: O(n log n), Space: O(n)

vector<int> bottomView(TreeNode* root) {
    if (!root) return {};
    map<int, int> hdToVal;
    queue<pair<TreeNode*, int>> q;
    q.push({root, 0});
 
    while (!q.empty()) {
        auto [node, hd] = q.front(); q.pop();
        hdToVal[hd] = node->val;   // Overwrite: last (deepest) wins
        if (node->left)  q.push({node->left,  hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    vector<int> result;
    for (auto& [hd, val] : hdToVal) result.push_back(val);
    return result;
}

class Codec {
public:
    // Serialize: preorder traversal with "#" for null
    string serialize(TreeNode* root) {
        if (!root) return "#";
        return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
    }
 
    // Deserialize: consume tokens in preorder order
    TreeNode* deserialize(string data) {
        queue<string> tokens;
        string token;
        for (char c : data) {
            if (c == ',') { tokens.push(token); token = ""; }
            else token += c;
        }
        tokens.push(token);  // Last token
        return buildTree(tokens);
    }
 
private:
    TreeNode* buildTree(queue<string>& tokens) {
        string tok = tokens.front(); tokens.pop();
        if (tok == "#") return nullptr;
        TreeNode* node = new TreeNode(stoi(tok));
        node->left  = buildTree(tokens);
        node->right = buildTree(tokens);
        return node;
    }
};
// Time: O(n) serialize, O(n) deserialize. Space: O(n).
 
/*
  Tree: 1 → 2 → null → null → 3 → null → null
  Serialized: "1,2,#,#,3,#,#"
 
  Deserialization trace:
  tok="1" → node(1)
    tok="2" → node(2)
      tok="#" → null (left of 2)
      tok="#" → null (right of 2)
    tok="3" → node(3)
      tok="#" → null (left of 3)
      tok="#" → null (right of 3)
  Result: 1→{2, 3} correctly reconstructed
*/

string serialize_level(TreeNode* root) {
    if (!root) return "";
    string result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        if (node) {
            result += to_string(node->val) + ",";
            q.push(node->left);
            q.push(node->right);
        } else {
            result += "#,";
        }
    }
    return result;
}

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
// Time: O(n), Space: O(h)

bool isSymmetric(TreeNode* root) {
    function<bool(TreeNode*, TreeNode*)> isMirror = [&](TreeNode* l, TreeNode* r) -> bool {
        if (!l && !r) return true;
        if (!l || !r) return false;
        return l->val == r->val
            && isMirror(l->left,  r->right)   // Outer pair
            && isMirror(l->right, r->left);   // Inner pair
    };
    return isMirror(root->left, root->right);
}
// Time: O(n), Space: O(h)

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}
// Time: O(n), Space: O(h)

bool hasPathSum(TreeNode* root, int target) {
    if (!root) return false;
    if (!root->left && !root->right) return root->val == target;
    return hasPathSum(root->left,  target - root->val)
        || hasPathSum(root->right, target - root->val);
}
// Time: O(n), Space: O(h)

int diameterOfBinaryTree(TreeNode* root) {
    int maxD = 0;
    function<int(TreeNode*)> h = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int l = h(node->left), r = h(node->right);
        maxD = max(maxD, l + r);
        return 1 + max(l, r);
    };
    h(root);
    return maxD;
}
// Time: O(n), Space: O(h)

bool isBalanced(TreeNode* root) {
    function<int(TreeNode*)> check = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int l = check(node->left);  if (l == -1) return -1;
        int r = check(node->right); if (r == -1) return -1;
        return abs(l - r) > 1 ? -1 : 1 + max(l, r);
    };
    return check(root) != -1;
}
// Time: O(n), Space: O(h)

vector<int> rightSideView(TreeNode* root) {
    if (!root) return {};
    vector<int> result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* node = q.front(); q.pop();
            if (i == sz - 1) result.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return result;
}
// Time: O(n), Space: O(n)

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int,int> inIdx;
    for (int i = 0; i < (int)inorder.size(); i++) inIdx[inorder[i]] = i;
 
    function<TreeNode*(int,int,int)> build = [&](int preStart, int inStart, int inEnd) -> TreeNode* {
        if (inStart > inEnd) return nullptr;
 
        int rootVal = preorder[preStart];
        TreeNode* root = new TreeNode(rootVal);
        int mid = inIdx[rootVal];              // Root's position in inorder
        int leftSize = mid - inStart;          // Size of left subtree
 
        root->left  = build(preStart + 1,             inStart,   mid - 1);
        root->right = build(preStart + 1 + leftSize,  mid + 1,   inEnd);
        return root;
    };
 
    return build(0, 0, inorder.size() - 1);
}
// Time: O(n), Space: O(n) — hash map for O(1) inorder index lookup
 
/*
  preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 
  build(preStart=0, inStart=0, inEnd=4):
    rootVal = preorder[0] = 3
    mid = inIdx[3] = 1  → left subtree: inorder[0..0] = [9], size=1
                        → right subtree: inorder[2..4] = [15,20,7], size=3
    left  = build(1, 0, 0):  rootVal=9, leaf
    right = build(2, 2, 4):  rootVal=20, ...
*/

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left  = lowestCommonAncestor(root->left,  p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}
// Time: O(n), Space: O(h)

int pathSum(TreeNode* root, long long targetSum) {
    unordered_map<long long,int> prefixCount;
    prefixCount[0] = 1;
    int count = 0;
    function<void(TreeNode*, long long)> dfs = [&](TreeNode* node, long long curr) {
        if (!node) return;
        curr += node->val;
        count += prefixCount[curr - targetSum];
        prefixCount[curr]++;
        dfs(node->left,  curr);
        dfs(node->right, curr);
        prefixCount[curr]--;   // Backtrack
    };
    dfs(root, 0);
    return count;
}
// Time: O(n), Space: O(n)

int maxPathSum(TreeNode* root) {
    int globalMax = INT_MIN;
    function<int(TreeNode*)> maxGain = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int leftGain  = max(0, maxGain(node->left));
        int rightGain = max(0, maxGain(node->right));
        globalMax = max(globalMax, node->val + leftGain + rightGain);
        return node->val + max(leftGain, rightGain);
    };
    maxGain(root);
    return globalMax;
}
// Time: O(n), Space: O(h)

class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "#";
        return to_string(root->val) + ","
             + serialize(root->left) + ","
             + serialize(root->right);
    }
    TreeNode* deserialize(string data) {
        queue<string> q;
        string tok;
        for (char c : data) {
            if (c == ',') { q.push(tok); tok = ""; }
            else tok += c;
        }
        q.push(tok);
        return build(q);
    }
private:
    TreeNode* build(queue<string>& q) {
        string t = q.front(); q.pop();
        if (t == "#") return nullptr;
        TreeNode* node = new TreeNode(stoi(t));
        node->left  = build(q);
        node->right = build(q);
        return node;
    }
};
// Serialize: O(n), Deserialize: O(n)