lca.cpp

/*
Lowest Common Ancestor (LCA)
Mathematical Foundation: LCA(u,v) = deepest node that is ancestor of both u,v
Binary Lifting: O(log n) query, O(n log n) preprocess
Euler Tour + RMQ: O(1) query, O(n log n) preprocess
Time: O(log n) per query
*/

#include <bits/stdc++.h>
using namespace std;

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

// LCA in Binary Tree - Simple DFS
// LeetCode: 236. Lowest Common Ancestor of a Binary Tree
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
// Related:
// 235. Lowest Common Ancestor of a Binary Search Tree
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
// 1644. Lowest Common Ancestor of a Binary Tree II
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/
// 1650. Lowest Common Ancestor of a Binary Tree III
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/
// 1676. Lowest Common Ancestor of a Binary Tree IV
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv/
// 865. Smallest Subtree with all the Deepest Nodes
// https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* l = lowestCommonAncestor(root->left, p, q);
    TreeNode* r = lowestCommonAncestor(root->right, p, q);
    return l && r ? root : l ? l : r;
}

// LCA in BST - Optimized
// LeetCode: 235. Lowest Common Ancestor of a Binary Search Tree
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
// Related:
// 236. Lowest Common Ancestor of a Binary Tree
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 1644. Lowest Common Ancestor of a Binary Tree II
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/
// 1650. Lowest Common Ancestor of a Binary Tree III
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/
// 938. Range Sum of BST
// https://leetcode.com/problems/range-sum-of-bst/
// 701. Insert into a Binary Search Tree
// https://leetcode.com/problems/insert-into-a-binary-search-tree/
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;
    }
    return nullptr;
}

// Binary Lifting LCA for Trees
// Related LeetCode Problems:
// 1483. Kth Ancestor of a Tree Node
// https://leetcode.com/problems/kth-ancestor-of-a-tree-node/
// 1123. Lowest Common Ancestor of Deepest Leaves
// https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
// 865. Smallest Subtree with all the Deepest Nodes
// https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/
// 1123. Lowest Common Ancestor of Deepest Leaves
// https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
// 2096. Step-By-Step Directions From a Binary Tree Node to Another
// https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
class LCA {
    vector<vector<int>> up;
    vector<int> depth;
    int LOG;
    
public:
    LCA(vector<vector<int>>& adj, int root) {
        int n = adj.size();
        LOG = __builtin_clz(1) - __builtin_clz(n) + 1;
        up.assign(n, vector<int>(LOG, -1));
        depth.assign(n, 0);
        
        function<void(int, int)> dfs = [&](int u, int p) {
            up[u][0] = p;
            for (int i = 1; i < LOG && up[u][i-1] != -1; i++)
                up[u][i] = up[up[u][i-1]][i-1];
            for (int v : adj[u]) if (v != p) {
                depth[v] = depth[u] + 1;
                dfs(v, u);
            }
        };
        dfs(root, -1);
    }
    
    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int i = 0; i < LOG; i++)
            if ((diff >> i) & 1) u = up[u][i];
        if (u == v) return u;
        for (int i = LOG - 1; i >= 0; i--) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
    
    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }
};

// Path Between Two Nodes
// LeetCode: 2096. Step-By-Step Directions From a Binary Tree Node to Another
// https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
// Related:
// 236. Lowest Common Ancestor of a Binary Tree
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 1026. Maximum Difference Between Node and Ancestor
// https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
// 543. Diameter of Binary Tree
// https://leetcode.com/problems/diameter-of-binary-tree/
// 687. Longest Univalue Path
// https://leetcode.com/problems/longest-univalue-path/
// 1123. Lowest Common Ancestor of Deepest Leaves
// https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
bool getPath(TreeNode* root, TreeNode* target, string& path) {
    if (!root) return false;
    if (root == target) return true;
    path.push_back('L');
    if (getPath(root->left, target, path)) return true;
    path.pop_back();
    path.push_back('R');
    if (getPath(root->right, target, path)) return true;
    path.pop_back();
    return false;
}

// Get Directions From Binary Tree Node to Another
// LeetCode: 2096. Step-By-Step Directions From a Binary Tree Node to Another
// https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/
// Related:
// 236. Lowest Common Ancestor of a Binary Tree
// https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 1026. Maximum Difference Between Node and Ancestor
// https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
// 543. Diameter of Binary Tree
// https://leetcode.com/problems/diameter-of-binary-tree/
// 687. Longest Univalue Path
// https://leetcode.com/problems/longest-univalue-path/
// 1123. Lowest Common Ancestor of Deepest Leaves
// https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/
string getDirections(TreeNode* root, int start, int dest) {
    string s, d;
    function<bool(TreeNode*, int, string&)> find = [&](TreeNode* node, int val, string& path) {
        if (!node) return false;
        if (node->val == val) return true;
        path += 'L';
        if (find(node->left, val, path)) return true;
        path.pop_back();
        path += 'R';
        if (find(node->right, val, path)) return true;
        path.pop_back();
        return false;
    };
    find(root, start, s);
    find(root, dest, d);
    int i = 0;
    while (i < s.size() && i < d.size() && s[i] == d[i]) i++;
    return string(s.size() - i, 'U') + d.substr(i);
}