Pair Sum Binary Search Tree

pair_sum_bst.py

from collections import deque


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


def link(node, array):
    if node is None:
        return 0
    s = link(node.left, array)
    array.append(node.value)
    s += link(node.right, array)
    return s + 1


def find_summation(tree, target):
    array = []
    left, right = 0, link(tree, array) - 1
    while left < right:
        s = array[left] + array[right]
        if s == target:
            return (array[left], array[right])
        elif s > target:
            right -= 1
        else:
            left += 1


def find_summation2(tree, target):
    search = set()
    queue = deque((tree.left, tree.right))

    while True:
        try:
            node = queue.popleft()
        except IndexError:
            return
        if node is None:
            continue
        y = target - node.value
        if y in search:
            return (node.value, y)
        queue.extend((node.left, node.right))
        search.add(node.value)


tree = Node(8, Node(3, Node(1, Node(-2)), Node(6, Node(4), Node(7))), Node(10, None, Node(14, Node(13), None)))

print(find_summation(tree, -1))
print(find_summation2(tree, -1))