134. Find the Closest Value to a Target in a BST

Given a binary search tree and a target value, find the value in the tree closest to the target. If two values are equally close, print the smaller one. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N). The target is given on the next line.

Input: First line contains space-separated level-order tokens describing the BST ('N' marks an absent child). Second line contains the target value. Output: Print a single integer - the value in the tree closest to the target.

1 <= number of nodes <= 10^5

This is a great example of how a BST's structure lets you PRUNE half the remaining search space at every single step, without ever needing to explicitly check both children - the same principle behind BST search, insertion, and the BST-specific LCA algorithm.

Find the value stored in a BST that is numerically closest to a given target. Brute force: Traverse the entire tree, checking every single node's distance to the target - this costs O(n), more than necessary given the BST's ordering property. Optimised: The BST property guarantees that at each step, you only need to move in ONE direction (never both) to find anything possibly closer - values on the 'wrong' side of the current node can never beat what's achievable by continuing in the correct direction, letting you find the closest value in time proportional to the tree's height.

Start at the root and walk downward exactly once: at each node, update the best-seen closest value (comparing distances and preferring the smaller value on ties), then move left if the target is smaller than the current node's value or right if it's larger, stopping when a null child is reached. Because a BST guarantees everything in a left subtree is smaller and everything in a right subtree is larger, this single downward path is guaranteed to pass close enough to the true answer without ever needing to look at the rest of the tree. It touches only the nodes along one root-to-leaf path instead of the whole tree. Time: O(h) Space: O(1)

Visit every node in the tree in any order (e.g. a simple recursive traversal) and, for each one, compute the absolute difference between its value and the target, keeping track of whichever value has produced the smallest difference so far (preferring the smaller value on ties). This is correct for any binary tree, not just a BST, because it never relies on ordering to prune anything - it simply checks every candidate. That generality is also its weakness: it visits all n nodes even though the BST structure would let us skip most of them. Time: O(n) Space: O(h)

Perform an inorder traversal to collect all values into an array; because it's a BST, this array comes out fully sorted for free. Then binary search that sorted array for the target to find the two candidate neighbours (the largest value ≤ target and the smallest value ≥ target) and compare their distances directly, breaking ties toward the smaller value. This exploits the BST's sortedness for a fast lookup once the array exists, but it still pays the cost of visiting and storing every node up front. Time: O(n) Space: O(n)

1. Start at the root, tracking a running 'best (closest) value found so far'. 2. At each node, update the best value if the current node is closer to the target than anything found before. 3. Move left if the target is smaller than the current node, or right if it's larger - continue until you fall off the tree.

Time: O(h), where h is the tree's height. Space: O(1) if implemented iteratively with a simple loop.

Test with the target exactly equal to a node's value, two tree values equidistant from the target (print the smaller one), and a tree with 10^5 nodes for performance.

Be precise about the exact tie-breaking rule stated (prefer the SMALLER value on a tie) - a small detail that's easy to miss if you're focused only on the distance comparison.