# straightforward O(klogN) solution with comment

• It uses two functions findPre() and findSuc() to get predecessor and successor node values given a target value. Then It obtains the closest value and gets the next closest value one by one.

``````  def closestKValues(self, root, target, k):

def findPre(cur, val, res):
if not cur: return
if cur.val == val:
# the maximum value in left subtree is predecessor
if cur.left:
tmp = cur.left
while(tmp.right):
tmp = tmp.right
res.append(tmp)
return
if cur.val > val:
findPre(cur.left, val, res)
else:
res.append(cur)
findPre(cur.right, val, res)

def findSuc(cur, val, res):
if not cur: return
if cur.val == val:
# the minimum value in right subtree is successor
if cur.right:
tmp = cur.right
while(tmp.left):
tmp = tmp.left
res.append(tmp)
return
if cur.val > val:
res.append(cur)
findSuc(cur.left, val, res)
else:
findSuc(cur.right, val, res)

if k == 0: return []
# find node value closet to target
cur = root
min_diff, closest = float("inf"), None
while cur:
if abs(cur.val - target) < min_diff:
min_diff = abs(cur.val - target)
closest = cur.val
if cur.val > target:
cur = cur.left
elif cur.val < target:
cur = cur.right
else:
closest = cur.val
break
# collect closest values from middle to the sides (left & right)
res = deque([closest])
while k > 1:
pre, suc = [], []
findPre(root, res[0], pre)
findSuc(root, res[-1], suc)

if not pre:
res.append(suc[-1].val)
elif not suc:
res.appendleft(pre[-1].val)
else:
if abs(pre[-1].val - target) < abs(suc[-1].val - target):
res.appendleft(pre[-1].val)
else:
res.append(suc[-1].val)
k -= 1
return list(res)
``````

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