bst.py

class Node:
    def __init__(self, info): 
        self.info = info  
        self.left = None  
        self.right = None 
        self.level = None 

    def __str__(self):
        return str(self.info) 

class BinarySearchTree:
    def __init__(self): 
        self.root = None

    def create(self, val):  
        if self.root == None:
            self.root = Node(val)
        else:
            current = self.root
         
            while True:
                if val < current.info:
                    if current.left:
                        current = current.left
                    else:
                        current.left = Node(val)
                        break
                elif val > current.info:
                    if current.right:
                        current = current.right
                    else:
                        current.right = Node(val)
                        break
                else:
                    break

# Enter your code here. Read input from STDIN. Print output to STDOUT
'''
class Node:
      def __init__(self,info): 
          self.info = info  
          self.left = None  
          self.right = None 
           

       // this is a node of the tree , which contains info as data, left , right
'''

def get_nodes(value, root):
  nodes = []
  while root.info != value:
    nodes.append(root)
    if value > root.info:
      root = root.right
    else:
      root = root.left
  return root, nodes


def get_value(node):
  return str(node.info)

def print_nodes(nodes):
  print('->'.join(map(get_value, nodes)))

def lca(root, v1, v2):
  v1_node, v1_nodes = get_nodes(v1, root)
  v2_node, v2_nodes = get_nodes(v2, root)

  if v1_node.left == v2_node or v1_node.right == v2_node:
    return v1_node
  elif v2_node.left == v1_node or v2_node.right == v1_node:
    return v2_node

  nodes = v2_nodes if len(v1_nodes) > len(v2_nodes) else v1_nodes
  if len(nodes) == 0:
    nodes = v1_nodes if len(v1_nodes) != 0 else v2_nodes
  return nodes.pop(0)

tree = BinarySearchTree()