Wednesday, December 18, 2019

Python Program to Find the Nearest Common Ancestor in the Given set of Nodes

Suppose we have a binary tree, so
the least common ancestor of the

i)               node 9 and node 6    =>    node 1

ii)              node 5 and node 9    =>    node 5

iii)            node 4 and node 6    =>    node 7

Definition of Nearest Common Ancestor

Let T be a binary tree. Let u and v be the nodes. The lowest common ancestor between two nodes u and v is defined as the lowest node In T that has both u and v as descendants. The Lca is the shared ancestor of u and v.


1.) If (node found)

       return node


       return Null

 2.) Traverse the nodes in Binary Tree using the inorder traversal i.e left -> parent ->   right node
      Again follow step 1

 3.) If the both node returns not null then it is the lowest common ancestor
      If at least one node returns Null then still we haven%u2019t got lowest common ancestor

The third point can be described using the below diagram:-

class Node: 
    def __init__(self,data): 
    #Assign data to the new node, set left and right children to None = data; 
        self.left = None; 
        self.right = None; 

def lowestCommonAncestor(root,n1,n2):        # Here, root represents the parent node

    # Step 1
    if(root is None):
        return None

    if( == n1 or
        return root

      # Step 2
    left = lowestCommonAncestor(root.left,n1,n2)
    right = lowestCommonAncestor(root.right,n1,n2)

     # Step 3 
    if left and right:     # Both nodes return some value, then we have got the lca [ where root is lca ]
        return root

     if left:                    # If one node returned NULL
         return left
         return right


root = Node(11); 
root.left = Node(12); 
root.right = Node(13); 
root.left.left = Node(14); 
root.left.right = Node(45); 
root.right.left = Node(64); 
root.right.right = Node(73);


Output :- 13

Arrays in Solidity Programming Language.

Arrays Solidity supports both generic and byte arrays. It supports both fixed size and dynamic arrays. It also supports multidimensional ...