#cs/cp #review
## Summary
Given a BST root, a target value, and an integer $k$, find the $k$ values closest to the target. Using an in-order traversal, we can treat this as a sliding-window problem.
## Example
$target=3.6,\ k=2,\ root=Node(4)$
```mermaid
graph TD
Nhhae0((4))
Nhhae1((2))
Nhhae2((5))
Nhhae3((1))
Nhhae4((3))
Nhhae0 --> Nhhae1
Nhhae0 --> Nhhae2
Nhhae1 --> Nhhae3
Nhhae1 --> Nhhae4
```
The return value will be $[3, 4]$.
## The Standard Approach: Deque — $O(N)$ Time
An in-order traversal of the BST allows us to evaluate the numbers sequentially, like a sorted list:
$[1,2,3,4,5]$
Next, we build our sliding window. Because we want the $k$ elements closest to our $target=3.6$, our window size is $k=2$. Let's examine the absolute differences from our $target$:
$[2.6, 1.6, 0.6, 0.4, 1.4]$
Because the numbers are evaluated in ascending order, their differences from the target form a V-shaped graph, behaving like $f(x) = |target - x|$.
As we slide our size-two window, we should include the next number if its absolute difference is smaller than the **front** of our deque. Once the next difference is larger, it means we are moving away from the target; we can stop searching and return the current window.
```tikz
\begin{document}
\begin{tikzpicture}[domain=0:5]
\draw[very thin,color=gray] (-0.5,-0.5) grid (4.9,4.9);
\draw[->] (-0.2,0) -- (4.9,0) node[right] {$x$};
\draw[->] (0,-0.2) -- (0,4.9) node[above] {$f(x)$};
\draw[color=blue, samples=200]
plot (\x,{abs(3.6-\x)})
node[right] {$f(x) =|3.6 - x|$};
\end{tikzpicture}
\end{document}
```
Let's trace this logic step-by-step. Assume we track both the node's value and its absolute difference from the $target$ (the visuals below display the absolute difference).
$i=0:$ Freely add $2.6$ for $Node(1)$.
```mermaid
graph LR
N0((2.6))
```
$i=1:$ Freely add $1.6$ for $Node(2)$.
```mermaid
graph LR
N0((2.6)) <--> N1((1.6))
```
$i=2:$ Remove $2.6$ for $Node(1)$ since $2.6 > 0.6$. Add $0.6$ for $Node(3)$.
```mermaid
graph LR
N0((1.6)) <--> N1((0.6))
```
$i=3:$ Remove $1.6$ for $Node(2)$ since $0.4 < 1.6$. Add $0.4$ for $Node(4)$.
```mermaid
graph LR
N0((0.6)) <--> N1((0.4))
```
$i=4:$ Consider $1.4$ for $Node(5)$, but since $1.4 > 0.6$, stop searching.
### Standard Deque Approach Code
```python
def closestKValues(self, root: Node, t: float, k: int) -> List[int]:
q = collections.deque()
def dfs(n):
if not n:
return False
# In-order traversal.
if dfs(n.left):
return True
q.append(n.val)
if len(q) > k:
# If the oldest candidate is closer than the newest one,
# all later values will also be too far away.
if abs(q[0] - t) < abs(q[-1] - t):
q.pop()
return True
q.popleft()
return dfs(n.right)
dfs(root)
return list(q)
```
This gives $O(N)$ worst-case time and $O(k+h)$ auxiliary space, where $h$ is the tree height. The traversal may stop early after passing the target.
## Advanced: $k$ Successors and $k$ Predecessors from Target — $O(h+k)$
To optimize, we can build [[BST Successor and Predecessor]] stacks while searching toward the target. The complexity is $O(h+k)$, or $O(\log N+k)$ for a balanced tree.
### Example
Let's try this with $target=12, k=3$.
```mermaid
%%{init: {'flowchart': {'curve': 'linear'}}}%%
graph TD
Nazi60((7))
Nazi61((2))
Nazi62((13))
Nazi63[ ]
style Nazi63 width:0px,fill:none,stroke:none
Nazi64((6))
Nazi65((9))
Nazi66((16))
Nazi67[ ]
style Nazi67 width:0px,fill:none,stroke:none
Nazi68[ ]
style Nazi68 width:0px,fill:none,stroke:none
Nazi69[ ]
style Nazi69 width:0px,fill:none,stroke:none
Nazi610[ ]
style Nazi610 width:0px,fill:none,stroke:none
Nazi611((8))
Nazi612((10))
Nazi60 --> Nazi61
Nazi60 --> Nazi62
Nazi61 ~~~ Nazi63
Nazi61 --> Nazi64
Nazi62 --> Nazi65
Nazi62 --> Nazi66
Nazi64 ~~~ Nazi69
Nazi64 ~~~ Nazi610
Nazi65 --> Nazi611
Nazi65 --> Nazi612
linkStyle 0,1,2,3,4,5,6 interpolate linear
```
This is the path we take when searching for $target=12$.
```mermaid
%%{init: {'flowchart': {'curve': 'linear'}}}%%
graph TD
Nudjq0((7))
style Nudjq0 fill:#ffff99,stroke:#333
Nudjq1((2))
Nudjq2((13))
style Nudjq2 fill:#ffff99,stroke:#333
Nudjq3[ ]
style Nudjq3 width:0px,fill:none,stroke:none
Nudjq4((6))
Nudjq5((9))
style Nudjq5 fill:#ffff99,stroke:#333
Nudjq6((16))
Nudjq7[ ]
style Nudjq7 width:0px,fill:none,stroke:none
Nudjq8[ ]
style Nudjq8 width:0px,fill:none,stroke:none
Nudjq9[ ]
style Nudjq9 width:0px,fill:none,stroke:none
Nudjq10[ ]
style Nudjq10 width:0px,fill:none,stroke:none
Nudjq11((8))
Nudjq12((10))
style Nudjq12 fill:#ffff99,stroke:#333
Nudjq13[ ]
style Nudjq13 width:0px,fill:none,stroke:none
Nudjq14[ ]
style Nudjq14 width:0px,fill:none,stroke:none
Nudjq15[ ]
style Nudjq15 width:0px,fill:none,stroke:none
Nudjq16[ ]
style Nudjq16 width:0px,fill:none,stroke:none
Nudjq17[ ]
style Nudjq17 width:0px,fill:none,stroke:none
Nudjq18[ ]
style Nudjq18 width:0px,fill:none,stroke:none
Nudjq19[ ]
style Nudjq19 width:0px,fill:none,stroke:none
Nudjq20[ ]
style Nudjq20 width:0px,fill:none,stroke:none
Nudjq21[ ]
style Nudjq21 width:0px,fill:none,stroke:none
Nudjq22[ ]
style Nudjq22 width:0px,fill:none,stroke:none
Nudjq23[ ]
style Nudjq23 width:0px,fill:none,stroke:none
Nudjq24[ ]
style Nudjq24 width:0px,fill:none,stroke:none
Nudjq25[ ]
style Nudjq25 width:0px,fill:none,stroke:none
Nudjq26((12))
style Nudjq26 stroke-dasharray: 5 5,stroke:#333
Nudjq27[ ]
style Nudjq27 width:0px,fill:none,stroke:none
Nudjq0 --> Nudjq1
Nudjq0 --> Nudjq2
Nudjq1 ~~~ Nudjq3
Nudjq1 --> Nudjq4
Nudjq2 --> Nudjq5
Nudjq2 --> Nudjq6
Nudjq4 ~~~ Nudjq9
Nudjq4 ~~~ Nudjq10
Nudjq5 --> Nudjq11
Nudjq5 --> Nudjq12
Nudjq6 ~~~ Nudjq13
Nudjq6 ~~~ Nudjq14
Nudjq11 ~~~ Nudjq23
Nudjq11 ~~~ Nudjq24
Nudjq12 ~~~ Nudjq25
Nudjq12 --> Nudjq26
linkStyle 0 interpolate linear
linkStyle 1 interpolate linear
linkStyle 2 interpolate linear
linkStyle 3 interpolate linear
linkStyle 4 interpolate linear
linkStyle 5 interpolate linear
linkStyle 6 interpolate linear
linkStyle 7 interpolate linear stroke-dasharray 5 5
```
> [!TIP] Visualizing the Predecessor and Successor Stacks
>
> The algorithm makes more sense if we visualize where the target would belong if it were inserted into the BST. Here, it would become the right child of $Node(10)$.
During the search, we populate two candidate stacks: the predecessor stack contains nodes where $node \leq target$, and the successor stack contains nodes where $node > target$.
```mermaid
%%{init: {'flowchart': {'curve': 'linear'}}}%%
graph TD
N0r8k0((7))
style N0r8k0 fill:#90ee90,stroke:#333,stroke-width:1px
N0r8k1((2))
N0r8k2((13))
style N0r8k2 fill:#ffff99,stroke:#333,stroke-width:1px
N0r8k3[ ]
style N0r8k3 width:0px,fill:none,stroke:none
N0r8k4((6))
N0r8k5((9))
style N0r8k5 fill:#90ee90,stroke:#333,stroke-width:1px
N0r8k6((16))
N0r8k7[ ]
style N0r8k7 width:0px,fill:none,stroke:none
N0r8k8[ ]
style N0r8k8 width:0px,fill:none,stroke:none
N0r8k9[ ]
style N0r8k9 width:0px,fill:none,stroke:none
N0r8k10[ ]
style N0r8k10 width:0px,fill:none,stroke:none
N0r8k11((8))
N0r8k12((10))
style N0r8k12 fill:#90ee90,stroke:#333,stroke-width:1px
N0r8k0 --> N0r8k1
N0r8k0 --> N0r8k2
N0r8k1 ~~~ N0r8k3
N0r8k1 --> N0r8k4
N0r8k2 --> N0r8k5
N0r8k2 --> N0r8k6
N0r8k4 ~~~ N0r8k9
N0r8k4 ~~~ N0r8k10
N0r8k5 --> N0r8k11
N0r8k5 --> N0r8k12
linkStyle 0,1,2,3,4,5,6 interpolate linear
```
$PredStack = [Node(7),Node(9),Node(10)]$. Notice that the top element of the predecessor stack is the largest element less than or equal to our target.
```mermaid
%%{init: {'flowchart': {'curve': 'linear'}}}%%
graph TD
Nwzpq0((7))
style Nwzpq0 fill:#ffff99,stroke:#333,stroke-width:1px
Nwzpq1((2))
Nwzpq2((13))
style Nwzpq2 fill:#90ee90,stroke:#333,stroke-width:1px
Nwzpq3[ ]
style Nwzpq3 width:0px,fill:none,stroke:none
Nwzpq4((6))
Nwzpq5((9))
style Nwzpq5 fill:#ffff99,stroke:#333,stroke-width:1px
Nwzpq6((16))
Nwzpq7[ ]
style Nwzpq7 width:0px,fill:none,stroke:none
Nwzpq8[ ]
style Nwzpq8 width:0px,fill:none,stroke:none
Nwzpq9[ ]
style Nwzpq9 width:0px,fill:none,stroke:none
Nwzpq10[ ]
style Nwzpq10 width:0px,fill:none,stroke:none
Nwzpq11((8))
Nwzpq12((10))
style Nwzpq12 fill:#ffff99,stroke:#333,stroke-width:1px
Nwzpq0 --> Nwzpq1
Nwzpq0 --> Nwzpq2
Nwzpq1 ~~~ Nwzpq3
Nwzpq1 --> Nwzpq4
Nwzpq2 --> Nwzpq5
Nwzpq2 --> Nwzpq6
Nwzpq4 ~~~ Nwzpq9
Nwzpq4 ~~~ Nwzpq10
Nwzpq5 --> Nwzpq11
Nwzpq5 --> Nwzpq12
linkStyle 0,1,2,3,4,5,6 interpolate linear
```
$SuccStack = [Node(13)]$.
Now, using the stacks, repeat the following $k$ times:
1. Examine the top nodes of the predecessor and successor stacks ($p$ and $s$).
2. Pop the element closest to the target (WLOG: $p$) and append it to our $ans$ array.
3. Perform the predecessor algorithm on $p$ (traverse to $p