Closest BST Values II - Miscellaneous / Tree Traversal without Recursion

Problems
1

https://algo.monster/problems/closest_bst_values_ii

3

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
4

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.

5

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.