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.
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 if (root == NULL) return NULL;
11 if (p->val > root->val && q->val > root->val) {
12 return lowestCommonAncestor(root->right, p, q);
13 } else if (p->val < root->val && q->val < root->val) {
14 return lowestCommonAncestor(root->left, p, q);
15 } else {
16 return root;
17 }
18}This C code implements the recursive approach by checking if both nodes' values are either greater or less than the current node. If so, recursively proceed to the right or left subtree, respectively. Otherwise, return the current node as the LCA.
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 <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
14 TreeNode* current = root;
15 while (current != NULL) {
16 if (p->val > current->val && q->val > current->val) {
17 current = current->right;
18 } else if (p->val < current->val && q->val < current->val) {
19 current = current->left;
20 } else {
21 return current;
22 }
23 }
24 return nullptr;
25 }
26};This C++ code iteratively travels through the tree by using a loop and logic checks based on node values to find the LCA.