Statementâ–¼
Given a binary search tree with n nodes, your task is to find the lowest common ancestor of two of its nodes, node1
and node2
.
The lowest common ancestor of two nodes, node1
and node2
, is defined as the lowest node in the binary search tree that has both node1
and node2
as descendants.
By definition, a node is a descendant of itself. For example, if node2
is a descendant of node1
, and we know that node1
is a descendant of itself, then node1
will be the lowest common ancestor of node1
and node2
.
Constraints:
- 2≤n≤500
- −103≤
Node.data
≤103 - All
Node.data
are unique. node1
î€ =node2
node1
andnode2
exist in the tree.
Solution
We will use Tree depth-first search to find the LCA of two nodes in a BST. The LCA is the lowest-level node that is a common ancestor of both node1
and node2
. In a BST, the nodes in the left subtree of any given node have values less than the node’s value, and the nodes in the right subtree have values greater than the node’s value. This BST property helps narrow down the search space, allowing us to identify the LCA effectively without having to explore the entire tree.
Since node1
and node2
are distinct values, and both must be present in the BST, there exist two cases where they can lie:
-
If one of the nodes is in the left subtree of the current node and the other is in the right subtree, then the current node itself will be the LCA.
-
If one of the nodes is an ancestor of the other node, then the parent node will be the LCA.
The steps of the algorithm above are given below:
- Initialize
current
with the root node. - We will start traversing the BST from the root node using
current
. While traversing, we will compare the value of thecurrent
node with the values ofnode1
andnode2
.- If the value of the
current
node is greater than the values of both nodes, it means the LCA lies in the left subtree of the current node, since both nodes must be present in the left subtree. Therefore, search for the LCA in the left subtree. - If the value of the
current
node is smaller than the values of both nodes, it means the LCA lies in the right subtree of the current node, since both nodes must be present in the right subtree. Therefore, search for the LCA in the right subtree. - If the value of the
current
node is between the values of both nodes (inclusive), it means thecurrent
itself is the LCA. Therefore, returncurrent
as the LCA ofnode1
andnode2
.
- If the value of the
- Continue the traversal until we find the LCA.
Let’s look at the following illustration to get a better understanding of the solution: