Question

Please show it with python

class Node

{

    int data;

    Node left, right;

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

public class BinaryTree {

// Root of the tree implemented in Node class

Node root;

Node findLowestCommonAncestor(int node1, int node2) {

    return findLowestCommonAncestor(root, node1, node2);

}

// This function returns pointer to LCA of two given

// values node1 and node2. This function assumes that node1 and

// node2 are present in Binary Tree

Node findLowestCommonAncestor(Node node, int node1, int node2) {

    /*

     * Base case condition ie. if The root itself is null then no point in checking further

     */

    if (node == null)

      return null;

    /*

     * If either node1 or node2 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 (node.data == node1 || node.data == node2)

      return node;

    // Look for keys in left and right subtrees

    Node left_lca = findLowestCommonAncestor(node.left, node1, node2);

    Node right_lca = findLowestCommonAncestor(node.right, node1, node2);

    /*

     * 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 != null && right_lca != null)

      return node;

    // else check if left subtree or right subtree is LCA

    return (left_lca != null) ? left_lca : right_lca;

}

   /*

   * Main class to test LCA functions

   */

   public static void main(String args[]) {

     BinaryTree tree = new BinaryTree();

     tree.root = new Node(1);//root node

     tree.root.left = new Node(500);//left child of root node

     tree.root.right = new Node(271);//right child of root node

     tree.root.left.left = new Node(21);//left child of left child of root node

     tree.root.left.right = new Node(203);//right child of left child of root node

     tree.root.right.left = new Node(553);//left leaf node

     tree.root.right.right = new Node(991);//right leaf node

     System.out.println("LCA(500, 271) = " + tree.findLowestCommonAncestor(500, 271).data);

     System.out.println("LCA(21, 203) = " + tree.findLowestCommonAncestor(21, 203).data);

     System.out.println("LCA(53 , 991) = " + tree.findLowestCommonAncestor(53 , 991).data);

     System.out.println("LCA(1, 991) = " + tree.findLowestCommonAncestor(1, 991).data);

   }

}

Answer 1

In case of any query do comment. Thanks

Code:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    def __str__(self):
        return self.data

class BinaryTree:
    #constructor
    def __init__(self):
        #Root of the tree implemented in Node class
        self.root = None
    
    def findLowestCommonAncestor(self,node1, node2):
        return self.findLowestCommonAncestorRecursive(self.root,node1,node2)
    
    #as python does not support function overloading the way Java supports hence using different name for the recursive function here
    #This function returns pointer to LCA of two given
    # values node1 and node2. This function assumes that node1 and
    # node2 are present in Binary Tree
    def findLowestCommonAncestorRecursive(self, node, node1, node2):
        #Base case condition ie. if The root itself is null then no point in checking further
        if node == None:
            return None
       
        #If either node1 or node2 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 node.data == node1 or node.data == node2:
            return node
        
        #Look for keys in left and right subtrees
        left_lca = self.findLowestCommonAncestorRecursive(node.left, node1, node2)
        right_lca = self.findLowestCommonAncestorRecursive(node.right, node1, node2)
        
        #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 != None and right_lca != None:
            return node
        #else check if left subtree or right subtree is LCA
        else:
            return left_lca if left_lca != None else right_lca

#main driver class
if __name__ == '__main__':
    tree = BinaryTree()
    tree.root = Node(1)#root node
    tree.root.left = Node(500)#left child of root node
    tree.root.right = Node(271)#right child of root node
    tree.root.left.left = Node(21)#left child of left child of root node
    tree.root.left.right = Node(203)#right child of left child of root node
    tree.root.right.left = Node(553)#left leaf node
    tree.root.right.right = Node(991)#right leaf node
    
    print("LCA(500, 271) = {}".format(tree.findLowestCommonAncestor(500, 271).data))
    print("LCA(21, 203) = {}".format(tree.findLowestCommonAncestor(21, 203).data))
    print("LCA(53 , 991) = {}".format(tree.findLowestCommonAncestor(53 , 991).data))
    print("LCA(1, 991) = {}".format(tree.findLowestCommonAncestor(1, 991).data))

    

============screen shot of the code=========

output: