Lowest common ancestor, how to build the tree from command line input?
<pre><code># 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) &gt; 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
</code></pre>

<p>The input on command line will be like this:</p>

<pre class="lang-none prettyprint-override"><code>6
D
F
A B
A C
B D
B E
E F
</code></pre>

<p>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.</p>

<p>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.</p>

<p>So, how could I read input through command line and build the same tree as I am able to do it through <code>root = Node('A')</code>, <code>root.left = Node('B')</code>, etc.?</p>

<p>I am trying to learn LCA, so would really appreciate some help in the right direction in a simplest way.</p>

<p>I'd recommend you use a dictionary or some other way to keep track of the members of the tree. </p>

<p>According to the way you build the tree, this is what I came up with: When you parse each ordered pair, </p>

<ul>
<li>Check whether the parent is in the tree or not. If the parent is present, check if there already exists a left child. 

<ul>
<li>If a left child exists, make the child the <em>right</em> child of the parent. </li>
<li>If a left child doesn't exist, make the child the <em>left</em> child of the parent.</li>
</ul></li>
<li>If the parent isn't present in the tree, it means that either the pair

<ul>
<li>Is the first one to be read, therefore the parent must be made the root, or</li>
<li>Contains an invalid parent.</li>
</ul></li>
</ul>

<p>Python-ish pseudocode (without error handling):</p>

<pre><code>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
</code></pre>

python algorithm tree binary-tree lowest-common-ancestor