Question

PYTHON CODING

Create a method for a Binary Search tree that finds the lowest common ancestor of two nodes in a tree (nodesLCA). The two nodes are input by the user identified by their values. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify its purpose.Illustrate the performance of the nodesLCA method. For the BST of datalist excute the method on following pairs: (500, 271), (21, 203) and (53 , 991)

class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
  
class BSTree():
def __init__(self, rootdata):
self.root = Node(rootdata)
  
def insert(self, data, cur_node):
if data < cur_node.data:
if cur_node.left == None:
cur_node.left = Node(data)
else:
self.insert(data, cur_node.left)
  
elif data > cur_node.data:
if cur_node.right == None:
cur_node.right = Node(data)
else:
self.insert(data, cur_node.right)
else:
print("Duplicate value!")

Answer 1

For Binary search tree, while traversing the tree from top to bottom the first node which lies in between the two numbers n1 and n2 is the LCA of the nodes, i.e. the first node n with the lowest depth which lies in between n1 and n2 (n1<=n<=n2) n1 < n2. So just recursively traverse the BST in, if node's value is greater than both n1 and n2 then our LCA lies in the left side of the node, if it's is smaller than both n1 and n2, then LCA lies on the right side. Otherwise, the root is LCA (assuming that both n1 and n2 are present in BST).

Algorithm:

1. Create a recursive function that takes a node and the two values n1 and n2.
2. If the value of the current node is less than both n1 and n2, then LCA lies in the right subtree. Call the recursive function for thr right subtree.
3. If the value of the current node is greater than both n1 and n2, then LCA lies in the left subtree. Call the recursive function for thr left subtree.
4. If both the above cases are false then return the current node as LCA.

Implementation:

# A recursive python program to find LCA of two nodes

# n1 and n2

# A Binary tree node

class Node:

    # Constructor to create a new node

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

# Function to find LCA of n1 and n2. The function assumes

# that both n1 and n2 are present in BST

def lca(root, n1, n2):

     

    # Base Case

    if root is None:

        return None

    # If both n1 and n2 are smaller than root, then LCA

    # lies in left

    if(root.data > n1 and root.data > n2):

        return lca(root.left, n1, n2)

    # If both n1 and n2 are greater than root, then LCA

    # lies in right

    if(root.data < n1 and root.data < n2):

        return lca(root.right, n1, n2)

    return root

# Driver program to test above function

NOTE:- This driver program doesn't contain your values you can change them easily by the above program. Please upvote if i helped you. thanks.

# Let us construct the BST

root = Node(20)

root.left = Node(8)

root.right = Node(22)

root.left.left = Node(4)

root.left.right = Node(12)

root.left.right.left = Node(10)

root.left.right.right = Node(14)

n1 = 10 ; n2 = 14

t = lca(root, n1, n2)

print "LCA of %d and %d is %d" %(n1, n2, t.data)

n1 = 14 ; n2 = 8

t = lca(root, n1, n2)

print "LCA of %d and %d is %d" %(n1, n2 , t.data)

n1 = 10 ; n2 = 22

t = lca(root, n1, n2)

print "LCA of %d and %d is %d" %(n1, n2, t.data)