PROBLEM DESCRIPTION
Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.
The successor of a node p is the node with the smallest key greater than p.val.
SOLUTION
APPROACH 1
We can create a min heap to store all nodes which have values more than p.val. The top most element will be the successor because the inorder has all sorted elements in a BST.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
// min heap
Queue<TreeNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
// in-order traversal
inorder(root, p, heap);
// if heap is empty, p must be the last visited node
// otherwise, the least element which is more than p.val must be the successor. This will be stored at the top of min heap (we have only added node to min heap if its value is more than p.val)
return (heap.size() == 0) ? null : heap.peek();
}
public Queue<TreeNode> inorder(TreeNode root, TreeNode p, Queue<TreeNode> heap){
// return if root is null
if(root == null)
return heap;
// look into left sub tree
inorder(root.left, p, heap);
// if current node value is more than p, add to heap
if(root.val > p.val){
heap.add(root);
}
// look into right sub tree
inorder(root.right, p, heap);
return heap;
}
}