Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

If this were a binary search tree, we could do a modified find on the two nodes and see where the paths diverge. Unfortunately, this is not a binary search tree, so we much try other ap- proaches. 

Attempt #1:
If each node has a link to its parent, we could trace p and q’s paths up until they intersect. 

Attempt #2:
Alternatively, you could follow a chain in which p and q are on the same side. That is, if p and q are both on the left of the node, branch left to look for the common ancestor. When p and q are no longer on the same side, you must have found the first common ancestor. 

__author__ = 'nitin'

def common_ancestor(root,node_p,node_q):
    if covers(root.getLeftChild(),node_p) and covers(root.getLeftChild(),node_q):
        return common_ancestor(root.getLeftChild(),node_p,node_q)
    if covers(root.getRightChild(),node_p) and covers(root.getRightChild(),node_q):
        return common_ancestor(root.getRightChild(),node_p,node_q)
    return root

def covers(root,node_p):
    if root is None:
        return False
    if root ==node_p:
        return True
    return covers(root.getLeftChild(),node_p) or covers(root.getRightChild(),node_p)
 

Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

__author__ = 'nitin'

def find_inorder_succ(node):
    if node is not None:
        if node.getRootVal() is None and node.getRightChild() is not None:
            p=left_most_child(node.getRightChild())
        else:
            p=node
            while p.getRootVal() is not None:
                if p.getLeftChild()==node:
                    break
                node=node.getRootVal()
                p=node
        return p
    return None

def left_most_child(node):
    if node is None:
        return None
    while node.getLeftChild() is not None:
        node=node.getLeftChild()
    return node