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)

Answer 1

Your BST is not given So, I am assuming my own BST [ You can change data as per your tree ]

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

# construct your 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 {} and {} is {}".format(n1, n2, t.data) )

#SAMPLE OUTPUT:

******************************************************************************************
PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION
******************************************************************************************