C++: Lowest Common Ancestor of a Binary Search Tree

Thought Process

The problem requires finding the lowest common ancestor (LCA) of two nodes in a Binary Search Tree (BST). The key property of a BST is that for any node, all values in the left subtree are smaller, and all values in the right subtree are larger. We use this property to determine the LCA. If both nodes are greater than the current root, we search in the right subtree. If both nodes are smaller, we search in the left subtree. Otherwise, the current root is the LCA. 

/**
 * Definition for a binary tree node.
 * 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 *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        // Both nodes are greater than root: Search in right sub tree
        if(root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right,p,q);
        // Both nodes are smaller than root: Search in left sub tree
        else if(root->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left,p,q);
        else
            return root;
    }
};

Code Complexity

Time Complexity: O(h)

The algorithm traverses the height of the tree, making it O(h), where 'h' is the height of the BST. In the worst case, this is O(n) for a skewed tree.

Space Complexity: O(h)

The algorithm uses recursion, which consumes stack space proportional to the height of the tree. In the worst case, this is O(n) for a skewed tree.

Code copied!