FAQs on Lowest Common Ancestor in a Binary Search Tree
Q: What is the Lowest Common Ancestor (LCA) in a Binary Search Tree (BST)?
A: The Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST) is the lowest node that has both the given nodes as descendants. In a BST, nodes are arranged such that the left child is smaller than the parent and the right child is greater than the parent.
Q: Why is finding the LCA important in a Binary Search Tree?
A: Finding the LCA in a Binary Search Tree is essential for various tasks such as determining the relationship between nodes, constructing balanced trees, and solving certain algorithmic problems efficiently.
Q: How can we find the LCA of two nodes in a Binary Search Tree?
A: To find the LCA of two nodes in a Binary Search Tree:
- Start traversing the tree from the root.
- If both nodes are greater than the current node, move to the right child.
- If both nodes are smaller than the current node, move to the left child.
- If one node is greater and the other is smaller than the current node, then the current node is their LCA.
Q: Can you provide an example code for finding the LCA in a Binary Search Tree?
A: Certainly! Here's a Python implementation to find the LCA of two nodes in a Binary Search Tree:
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def find_lca(root, node1, node2):
if root is None:
return None
if root.key > node1 and root.key > node2:
return find_lca(root.left, node1, node2)
elif root.key < node1 and root.key < node2:
return find_lca(root.right, node1, node2)
else:
return root.key
# Example usage:
# Constructing a BST
root = TreeNode(20)
root.left = TreeNode(10)
root.right = TreeNode(30)
root.left.left = TreeNode(5)
root.left.right = TreeNode(15)
root.right.left = TreeNode(25)
root.right.right = TreeNode(35)
# Finding the LCA of nodes 5 and 15
lca = find_lca(root, 5, 15)
print("LCA of 5 and 15:", lca) # Output: 10
This code defines a TreeNode class for constructing the Binary Search Tree and a function find_lca to find the LCA of two nodes.
Important Interview Questions and Answers on Lowest Common Ancestor in a Binary Search Tree
Q: What is the Lowest Common Ancestor (LCA) in a Binary Search Tree?
The Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST) is the node furthest from the root that is an ancestor of both nodes.
Q: How can you find the Lowest Common Ancestor in a Binary Search Tree?
To find the LCA of two nodes in a BST, we traverse the tree from the root and compare the values of the two nodes with the current node:
- If both nodes are less than the current node's value, we move to the left subtree.
- If both nodes are greater than the current node's value, we move to the right subtree.
- If one node is less and the other is greater than the current node's value, it means the current node is the LCA.
Q: Can you provide the algorithm to find the Lowest Common Ancestor in a Binary Search Tree?
Here is the code.
Algorithm LCA(root, p, q):
1. Start traversing the tree from the root.
2. If both p and q are less than the current node's value, move to the left subtree.
3. If both p and q are greater than the current node's value, move to the right subtree.
4. If one node is less and the other is greater than the current node's value, return the current node as the LCA.
Q: What is the time complexity of finding the Lowest Common Ancestor in a Binary Search Tree?
The time complexity of finding the LCA in a BST is O(h), where h is the height of the tree.
Q: Can you provide an example code for finding the Lowest Common Ancestor in a Binary Search Tree?
Here is the code.
# 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
def lowestCommonAncestor(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
# Example usage:
# Construct the binary search tree
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)
p = root.left
q = root.right
lca_node = lowestCommonAncestor(root, p, q)
print("Lowest Common Ancestor:", lca_node.val) # Output: 6
This example code demonstrates how to find the Lowest Common Ancestor of two nodes in a Binary Search Tree and prints the value of the LCA node.
