# Python program to find LCA of n1 and n2 using one
# traversal of Binary tree
# def build_graph():
# n = input()
# ex1, ex2 = raw_input(), raw_input()
# d = {}
# for i in xrange(n-1):
# e1, e2 = map(str, raw_input().split())
# if e1 not in d:
# node = Node(e1)
# node.left = Node(e2)
# d.update({e1:node})
# if e1 in d:
# d[e1].right = Node(e2)
# # for i in d.values():
# # print i.key, i.left.left.key, i.right.key
# print d.get(next(d.__iter__()))
# return d
def build_graph():
l = []
n = input()
ex1, ex2 = raw_input(), raw_input()
for i in xrange(n-1):
e1, e2 = map(str, raw_input().split())
node1 = Node(e1)
node2 = Node(e2)
if len(l) > 0:
if node1 not in l:
node1.left = node2
l.append(node1)
if e1 in d:
# 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):
# print graph
# if type(graph) is dict:
# root = graph.popitem()
# root = root[1]
# else:
# root = graph
# Base Case
if root is None:
return root
# 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 and right_lca:
return root
# Otherwise check if left subtree or right subtree is LCA
return left_lca if left_lca is not None else right_lca
# Driver program to test above function
# Let us create a binary tree given in the above example
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')
root.left.left.left = Node('F')
# root.left.left.right = Node('F')
build_graph() # not being used not but want to take input and build a tree
print findLCA(root , 'Hilary', 'James').key
The input on command line will be like this:
6
D
F
A B
A C
B D
B E
E F
As you could see, I could hardcode it, by using Node class, but I want to build the tree using command line input as mentioned above.
INPUT FORMAT: The first number is the number of unique people in a family. And, then the two selected people in a family, i.e; D,F, and then the rest of the lines contains name of two people with a space separator. A B means, A is senior to B, and B is senior to E and D etc. For simplicity the first set that is A B, A has to be considered as root of the tree.
So, how could I read input through command line and build the same tree as I am able to do it through root = Node('A'), root.left = Node('B'), etc.?
I am trying to learn LCA, so would really appreciate some help in the right direction in a simplest way.
I'd recommend you use a dictionary or some other way to keep track of the members of the tree.
According to the way you build the tree, this is what I came up with: When you parse each ordered pair,
Python-ish pseudocode (without error handling):
members = {}
for line in input:
parent_key, child_key = line.split(' ')
if parent_key not in members:
# I'm assuming this will happen only for
# the first pair
root = members[parent_key] = Node(parent_key)
parent = members[parent_key]
if parent.left is None:
# If the child already exists, don't create a new one
# You can change this and the next statement if this isn't what you want
# This also assumes that the given child, if exists
# is not already a child of any member
# If that can happen, you'll need to keep track of parents too
parent.left = members.get(child_key, Node(child_key))
members[child_key] = parent.left
else:
# Assuming that the parent will not have
# a right child if we're here
parent.right = members.get(child_key, Node(child_key))
members[child_key] = parent.right