DoorDash Coding Question: Closest BST Node to Target

You are given the root of a Binary Search Tree (BST) and a floating-point target. Your task is to return the integer node value from the tree that is closest to the target by absolute difference |v - target|. For example, given [4,2,5,1,3] and target 3.714286, you should return 4.

Core idea: use the BST ordering to guide a near O(height) search. At each node compare its value to the target, update the best (closest) value so far, then move left if target < node.val or right if target > node.val. Because a BST partitions smaller and larger values, you avoid scanning irrelevant subtrees.

Flow you should follow in an interview:

• Clarify assumptions (can tree be empty, duplicate values, precision/tie-breaking).
• Describe approaches: iterative BST walk (O(h) time, O(1) extra space), recursive variant (O(h) time, O(h) call stack), and a full in-order to array + binary search approach (O(n) preprocess, O(log n) per query) if you must answer many targets.
• Write code, handle edge cases (single-node tree, negative/large floats) and analyze complexity.

Skill signals interviewers look for: correct use of BST properties, clear time/space complexity reasoning (average O(log n) time; worst-case O(n)), careful handling of floating-point comparisons, and clean iterative implementation to avoid unnecessary recursion depth.