Approach: We don't have to use bottom-up / Post order traversal approach here like we did in finding LCA of Binary Tree. We can use following property of BST to simplify it:
node.Left.Value < node.Value < node.Right.Value
So we can use top-bottom approach. At each node, we can have one of the following conditions:
- Both of the input nodes' values are less than current node value. In this case we just have to go to current node's left and search there.
- Both of the input nodes' values are greater than current node value. In this case we just have to go to current node's right and search there.
- We got our node
Implementation in C#:
public new BinaryTreeNode LowestCommonAncestor(BinaryTreeNode p, BinaryTreeNode q)
{
if (this.Root == null)
{
return null;
}
return this.LowestCommonAncestor(this.Root, p, q);
}
private new BinaryTreeNode LowestCommonAncestor(BinaryTreeNode node, BinaryTreeNode p, BinaryTreeNode q)
{
if (node == null)
{
return null;
}
if (node.Value < p.Value && node.Value < q.Value)
{
return this.LowestCommonAncestor(node.RightNode, p, q);
}
else if (node.Value > p.Value && node.Value > q.Value)
{
return this.LowestCommonAncestor(node.LeftNode, p, q);
}
else
{
return node;
}
}
Complexity: O(n)
No comments:
Post a Comment