# two pointers on BST, O(n) time, O(lgn) average space

• ``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
# # using hash set
# vals = set()
# def inorder(node):
#     if node:
#         if inorder(node.left):
#             return True
#         if k - node.val in vals:
#             return True
#         if inorder(node.right):
#             return True
#     return False
# return inorder(root)

# two pointer
stack_forward = []
stack_backward = []
p = root
while p:
stack_forward.append(p)
p = p.left
p = root
while p:
stack_backward.append(p)
p = p.right
while stack_forward and stack_backward:
if stack_forward[-1].val == stack_backward[-1].val:
break
if stack_forward[-1].val + stack_backward[-1].val == k:
return True
if stack_forward[-1].val + stack_backward[-1].val < k:
p = stack_forward.pop().right
while p:
stack_forward.append(p)
p = p.left
else:
p = stack_backward.pop().left
while p:
stack_backward.append(p)
p = p.right
return False

``````

• Just wanted to see how it would look when I separate the three parts (forward iteration, backward iteration, and main algorithm)...

``````def findTarget(self, root, k):

def forward(root):
stack = []
p = root
while p:
stack.append(p)
p = p.left
while stack:
yield stack[-1].val
p = stack.pop().right
while p:
stack.append(p)
p = p.left
yield None

def backward(root):
stack = []
p = root
while p:
stack.append(p)
p = p.right
while stack:
yield stack[-1].val
p = stack.pop().left
while p:
stack.append(p)
p = p.right
yield None

forward = forward(root)
backward = backward(root)
f, b = next(forward), next(backward)
while f is not None is not b:
if f == b:
break
if f + b == k:
return True
if f + b < k:
f = next(forward)
else:
b = next(backward)
return False``````

• And another version...

``````def findTarget(self, root, k):

def vals(root, forward=True):
stack = []
p = root
while p or stack:
while p:
stack.append(p)
p = p.left if forward else p.right
p = stack.pop()
yield p.val
p = p.right if forward else p.left
yield None

forward = vals(root)
backward = vals(root, forward=False)
f, b = next(forward), next(backward)
while f != b:
if f + b == k:
return True
if f + b < k:
f = next(forward)
else:
b = next(backward)
return False``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.