Why do you need a stack? I think the solution I have is cleaner. reference: https://www.youtube.com/watch?v=uIkji391mBI&ab_channel=CrackingFAANG
from typing import List
from collections import deque
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def closest_values(bst: Node, target: int, k: int) -> List[int]:
# WRITE YOUR BRILLIANT CODE HERE
q = deque()
def dfs(node):
if node is None:
return
dfs(node.left)
# q is empty
if len(q) < k:
q.append(node.val)
else:
# q is filled with k
# check if the first node in q (most distant node as the BST inorder gives sorted node.vals)
# is further away than current node
if abs(q[0] - target) > abs(node.val - target):
q.popleft()
q.append(node.val)
#else:
# return
dfs(node.right)
dfs(bst)
return q