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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, 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# solution employs recursion to traverse the BST. It checks conditions by comparing node values and recursively moves down left or right until the LCA is found.
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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var lowestCommonAncestor = function(root, p, q) {
7 let current = root;
8 while (current) {
9 if (p.val > current.val && q.val > current.val) {
10 current = current.right;
11 } else if (p.val < current.val && q.val < current.val) {
12 current = current.left;
13 } else {
14 return current;
15 }
16 }
17 return null;
18};This JavaScript solution utilizes iteration with a loop to traverse the tree and determine the LCA by checking node relations and switching paths accordingly.