235. Lowest Common Ancestor of a Binary Search Tree - cocoder39/coco39_LC GitHub Wiki

235. Lowest Common Ancestor of a Binary Search Tree

time complexity is O(h) where h is height of bst, space complexity is O(h) because of call stack, which can be optimized through iterative solution

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p == nullptr) {
            return q;
        } else if (q == nullptr) {
            return p;
        } else if (p == nullptr && q == nullptr) {
            return nullptr;
        } else if (root == nullptr) {
            return nullptr;
        }
        
        if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else if (root->val > p->val && root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else {
            return root;
        }
    }

iterative solution with O(h) time complexity and O(1) space complexity

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p == nullptr) {
            return q;
        } else if (q == nullptr) {
            return p;
        } else if (p == nullptr && q == nullptr) {
            return nullptr;
        }
        
        while (root) {
            if (root->val < p->val && root->val < q->val) {
                root = root->right;
            } else if (root->val > p->val && root->val > q->val) {
                root = root->left;
            } else {
                return root;
            }
        }
        return root;
    }
⚠️ **GitHub.com Fallback** ⚠️