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
The title says ‘Without recursion’, so I guess that’s the trick.
The two loops + stack is a ‘workaround’ to make in-order traversal without recursion.
Please be nice when you disagree without others, and avoid rhetorical tonality, even if your solution is cleaner.
‘Why do you’ conveys micro-contempt and aggression. You can instead say, ‘Why don’t you’ and just state your solution.
in-order traversal is the most obvious solution, but this question is meant to show how to traverse without recursion as the title states.
also, there is a leet code question that asks you to build a binary search tree iterator in O(height of the tree), in which case, stack is the only option. so there is some value in the stack solution even if it’s not the cleanest.
I find the question misleading because I initially thought it meant the exact opposite. Since it says, “Do not convert the BST to a list,” I assumed we couldn’t use a stack. While I thought we were limited to recursion, the topic seems to be about learning to avoid using it.