235. Lowest Common Ancestor of a Binary Search Tree

📝 Problem Details

• Title: 235. Lowest Common Ancestor of a Binary Search Tree
• Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
• Difficulty: Medium
• Tags/Categories: BST Recursion DFS Trees

💭What Were My Initial Thoughts?

- BST definition: 
	- nodes is the left subtree are less than the parent
	- nodes in the right subtree are greater than the parent

- Lowest Common Ancestor (LCA):
	- need to find the lowest node that has both p and q as its descendants
	- a node can be a descendant of itself

💡 Explanation of Solution

1. base case: if root is null then return null
2. check psition of p and q in the BST
	- if both p and q are smaller than the root, search in the left subtree
	- if both p and q are greater than the root, search in the right subtree
	- otherwise, return the root since we can confirm its the LCA because p and q are on different sides (or one of them is the root itself)

⌛ Complexity Analysis

Time Complexity:
	balanced BST: we eliminate half the tree at each step --> O(log N)
	skewed BST: degenerated Linked List which would have a worst case traversal of O(N)

Space Complexity: Worst case of O(n)

💻 Implementation of Solution

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
 
        if(root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right, p, q);
        
        if(root->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left, p, q);
        
        return root;
    }
};