Lowest Common Ancestor in Binary tree - Python

Python program to find Lowest Common Ancestor (LCA) of n1 and n2 using one traversal of Binary tree

Lowest Common Ancestor in Python for a binary tree

Implementation Involves:- We find LCA of binary tree using recursive approach. We created a function returns pointer to LCA of two given values n1 and n2, it assumes that n1 and n2 are present in Binary Tree. If either n1 or n2 matches with root's key, it will tell presence by returning root. Then it will Look for keys in left and right subtrees, and according to the function it will tell whether the one key is present in once subtree and other is present in other or check if left subtree or right subtree is LCA.

Requirements:
1. Python 3.x

2. A text editor

How to Run:
1. Create a project in your text editor named binary_LCA and implement this python code in binary_LCA.py.
2. Run the file by writing the command on terminal "python filename.py".

Code

# Python program to find LCA of n1 and n2 using one
# traversal of Binary tree
# A binary tree node
class Node:
     
    # Constructor to create a new tree node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
     
# This function returns pointer to LCA of two given
# values n1 and n2
# This function assumes that n1 and n2 are present in
# Binary Tree
def findLCA(root, n1, n2):
     
    # Base Case
    if root is None:
        return None
 
    # If either n1 or n2 matches with root's key, report
    #  the presence by returning root (Note that if a key is
    #  ancestor of other, then the ancestor key becomes LCA
    if root.key == n1 or root.key == n2:
        return root
 
    # Look for keys in left and right subtrees
    left_lca = findLCA(root.left, n1, n2) 
    right_lca = findLCA(root.right, n1, n2)
 
    # If both of the above calls return Non-NULL, then one key
    # is present in once subtree and other is present in other,
    # So this node is the LCA
    if (left_lca is not None) and (right_lca is not None):
        return root
 
    # Otherwise check if left subtree or right subtree is LCA
    return left_lca if left_lca is not None else right_lca
 

Output

Lowest Common Ancestor in Binary tree - Python

Project Files

Comments (0)

Leave a Comment

Rating

Author

	..

This directory is empty.