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

    def insert(self, x):
        if x < self.val:
            if self.left == None:
                self.left = Node(x)
            else:
                self.left.insert(x)
        elif x > self.val:
            if self.right == None:
                self.right = Node(x)
            else:
                self.right.insert(x)

    def has(self, x):
        if x < self.val and self.left != None:
            return self.left.has(x)
        elif x > self.val and self.right != None:
            return self.right.has(x)
        if self.val == x:
            return True
        else:
            return False

def find_CA(root, a, b): #finds Common Ancestor

    if root.val > a and root.val > b:
        return find_CA(root.left, a, b)
    elif root.val < a and root.val < b:
        return find_CA(root.right, a, b)
    return root

def shortest_path(root, a, b):
    ca = find_CA(root, a, b)
    return path(ca, a, b)

def path(ca, a, b):
    p = []
    ca_to_leaf(ca, a, p)
    p.reverse()
    p.pop() #to avoid repeated common ancestor on p
    ca_to_leaf(ca, b, p)
    return p

def ca_to_leaf(ca, end, p):
    if ca.val == end:
        p.append(end)

    else:
        p.append(ca.val)
        if end < ca.val:
            ca_to_leaf(ca.left, end, p)
        else:
            ca_to_leaf(ca.right, end, p)

##test##
#creates tree
x = Node(8)
for i in [3,10,1,6,14,7,13]:
    x.insert(i)

#              8
#            /    \
#         3          10
#       /   \          \
#      1     6           14
#              \         /
#                7     13
#

print(shortest_path(x, 13, 7))
print(shortest_path(x, 7, 13))
print(shortest_path(x, 1, 7))