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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var lowestCommonAncestor = function(root, p, q) {
7 if (!root) return null;
8 if (p.val > root.val && q.val > root.val)
9 return lowestCommonAncestor(root.right, p, q);
10 else if (p.val < root.val && q.val < root.val)
11 return lowestCommonAncestor(root.left, p, q);
12 else
13 return root;
14};This JavaScript solution leverages the BST properties in a recursive function to find the LCA by logical determination of node positions relative to p and q values.
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.
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 current = root
10 while current:
11 if p.val > current.val and q.val > current.val:
12 current = current.right
13 elif p.val < current.val and q.val < current.val:
14 current = current.left
15 else:
16 return current
17 return NoneThis Python code employs a loop to iteratively navigate the BST using comparisons to find the LCA, which ensures efficient space usage.