closest-binary-search-tree-value-ii

< Previous 　　　　　　　　　　　　　　　　 Next >

272. Closest Binary Search Tree Value II (Hard)

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

• Given target value is a floating point.
• You may assume k is always valid, that is: k ≤ total nodes.
• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Related Topics

[Stack] [Tree] [Depth-First Search] [Binary Search Tree] [Two Pointers] [Binary Tree] [Heap (Priority Queue)]

Similar Questions

1. Binary Tree Inorder Traversal (Easy)
2. Closest Binary Search Tree Value (Easy)

Hints

Hint 1

Consider implement these two helper functions:

1. getPredecessor(N), which returns the next smaller node to N.
2. getSuccessor(N), which returns the next larger node to N.

Hint 2

Try to assume that each node has a parent pointer, it makes the problem much easier.

Hint 3

Without parent pointer we just need to keep track of the path from the root to the current node using a stack.

Hint 4

You would need two stacks to track the path in finding predecessor and successor node separately.