Lowest Common Ancestor Of Binary Tree In Python | letsbug

     Hey in the article we are looking at a coding challenge problem. You might have come across this it is called finding the lowest common ancestor in a binary tree. 

    So we will find the solution to this problem in python. Let's start. The answer is simple we have to visit every node and check if its child is same as it is asked if so then you return the node and we repeat this process for subtrees of  the tree and then if left and right node exit we return it. to the top.

code: 

class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
class binaryTree:
    def __init__(self):
        self.root = None
    #inserts a node in binary tree
    def insert(self,data):
        if(self.root == None):
            self.root = Node(data)
        else:
            self.insertNode(data,self.root)

    Above is boilerplate code for the binary tree we are not focused on that now lets see 

Lowest Common Ancestor 

code: 

#Lowest common ancestor of binary tree
def lca(self, root, n1, n2):
    if root is None: # Base case
        return None 
    if root.data == n1 or root.data == n2: # Base case
        return root
    left = self.lca(root.left, n1, n2) # Recursive call for left subtree
    right = self.lca(root.right, n1, n2) # Recursive call for right subtree
    if left and right: # If both left and right subtrees contain one of the nodes
        return root
    # Return left subtree if left subtree contains node, else return right subtree
    return left if left else right


#lowest common ancestor of binary tree
print("Lowest Common Ancestor of binary tree is:")
print(tree.lca(tree.root, 10, 20))

        

    Above code is for finding lowest common ancestor of binary tree now you can initialize it and run it. I have initialize the binary tree with random numbers and called the lca function and go this output.

output:

Lowest Common Ancestor of binary tree is:
None

☺👆