Coders Packet

Lowest Common Ancestor in Binary tree - Python

By PRIYA KUMARI

  • binary lca/
  • 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

    binary-LCA_output

    Download Complete Code

    Comments

    Comments for the packet "Lowest Common Ancestor in Binary tree - Python";
    No comments yet