This method exploits the properties of a BST. The idea is to traverse the tree starting from the root. If both p and q are greater than the current node, then the LCA lies in the right subtree. If both are smaller, then it lies in the left subtree. Otherwise, the current node is the LCA.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to the recursion stack.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
9 if not root:
10 return None
11
12 if p.val > root.val and q.val > root.val:
13 return self.lowestCommonAncestor(root.right, p, q)
14 elif p.val < root.val and q.val < root.val:
15 return self.lowestCommonAncestor(root.left, p, q)
16 else:
17 return rootThis Python function uses recursion to navigate the tree, choosing branches based on node values. The LCA is found by determining when p and q reside on different sides of a node.
Instead of recursion, this method uses a while loop to traverse the tree. Starting from the root, check if both nodes are greater or smaller than the current node to decide whether to proceed to the right or left subtree respectively. If neither, we've found the LCA.
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(1) since it does not use extra space beyond variables.
1#include <stdio.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode *right;
7};
8
9struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
10 struct TreeNode* current = root;
11 while (current != NULL) {
12 if (p->val > current->val && q->val > current->val) {
13 current = current->right;
14 } else if (p->val < current->val && q->val < current->val) {
15 current = current->left;
16 } else {
17 return current;
18 }
19 }
20 return NULL;
21}This C implementation uses an iterative approach via a loop to find the LCA. It makes use of BST properties to decide movement between left and right nodes.