kth element in binary search tree

# Find kth smallest element in a binary search tree

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

    def __repr__(self):
        fmt = "{%d" % self.v

        if self.left:
            fmt += " L:%s" % str(self.left)

        if self.right:
            fmt += " R:%s " % str(self.right)

        fmt += "}"

        return fmt

FOUND_NODE = 0
NUM_CHILDREN = 1
DOESNT_MATTER = -1

# returns a tuple of (found_node, num_children)
# found_node = result
# num_children = helper return value to support recursive algorithm
def kth(root, k):
    if not root:
        return (None, 0)

    L = kth(root.left, k)

    if L[FOUND_NODE]:
        return L

    if L[NUM_CHILDREN] == k: # num children on the left subtree
        return (root, DOESNT_MATTER)

    R = kth(root.right, k - (1+L[NUM_CHILDREN]) )
    return (R[FOUND_NODE], 1 + R[NUM_CHILDREN] + L[NUM_CHILDREN])

def tree_from_sorted(seq, begin, end):

    N = end - begin
    if N == 1:
        return Node(seq[begin])

    pos = begin + N/2
    return Node(seq[pos],
        tree_from_sorted(seq, begin, pos),
        tree_from_sorted(seq, pos+1, end))

N = 15
v = [i for i in range(N)]
tree = tree_from_sorted(v, 0, len(v))
print tree

for i in range(N):
    node = kth(tree, i)[FOUND_NODE]
    print i, node.v