Dare2Solve
Given a binary search tree (BST) and two nodes, p
and q
, find their lowest common ancestor (LCA). The LCA of two nodes p
and q
in a BST is defined as the lowest node in the tree that has both p
and q
as descendants (where we allow a node to be a descendant of itself).
In a binary search tree, for any given node N
, all the nodes in the left subtree of N
have values less than N.val
, and all the nodes in the right subtree of N
have values greater than N.val
. This property allows us to efficiently find the LCA by navigating the tree based on the values of p
and q
.
p
and q
are smaller than N
, then their LCA must be in the left subtree.p
and q
are greater than N
, then their LCA must be in the right subtree.p
and q
are on different sides of N
, or if one of them is equal to N
, then N
is the LCA.p
and q
:
p
and q
are smaller than the current node's value, move to the left child.p
and q
are greater than the current node's value, move to the right child.p
and q
are on different sides, or if one of them matches the current node, then the current node is the LCA.O(h), where h
is the height of the tree. In the worst case, the algorithm may need to traverse from the root to a leaf node, which would take h
steps.
O(1), since the solution only uses a constant amount of extra space.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root) {
if (root->val < p->val && root->val < q->val) {
root = root->right;
}
else if (root->val > p->val && root->val > q->val) {
root = root->left;
} else {
break;
}
}
return root;
}
};
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
while root:
if root.val < p.val and root.val < q.val:
root = root.right
elif root.val > p.val and root.val > q.val:
root = root.left
else:
break
return root
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (root.val < p.val && root.val < q.val) {
root = root.right;
} else if (root.val > p.val && root.val > q.val) {
root = root.left;
} else {
break;
}
}
return root;
}
}
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
if (!root) return null;
while (root) {
if (root.val < p.val && root.val < q.val) {
root = root.right;
}
else if (root.val > p.val && root.val > q.val) {
root = root.left;
} else {
break;
}
}
return root;
};