Question
A binary search tree is given. Find the ceiling of given key. Eg.
8
3 12
2 6 10 15
4
Ceiling is defined as:
Ceil Value Node: Node with smallest data larger than the key value.
Testing:
key - 13 => 15
key - 4 =>6
key - 8 =>10
Solution
A really interesting idea is to go top-to-bottom, and update value in every left turn only. Suggested by the top answer.
It’s a very very tricky solution. I’ve never seen this b4.
Code
Not my code.
public int findCeil(TreeNode node, int num, int found) {
if (node != null) {
if (num >= node.val)
return findCeil(node.right, num, found);
else
return findCeil(node.left, num, node.val);
} else
return found;
}
Now input:
TreeNode tree = Common.constructBstFromPreorder(new int[] { 40, 20, 10, 30, 60, 50, 70 });
Output:
The ceiling of 0 is 10
The ceiling of 1 is 10
The ceiling of 2 is 10
The ceiling of 3 is 10
The ceiling of 4 is 10
The ceiling of 5 is 10
The ceiling of 6 is 10
The ceiling of 7 is 10
The ceiling of 8 is 10
The ceiling of 9 is 10
The ceiling of 10 is 20
The ceiling of 11 is 20
The ceiling of 12 is 20
The ceiling of 13 is 20
The ceiling of 14 is 20
The ceiling of 15 is 20
The ceiling of 16 is 20
The ceiling of 17 is 20
The ceiling of 18 is 20
The ceiling of 19 is 20
The ceiling of 20 is 30
The ceiling of 21 is 30
The ceiling of 22 is 30
The ceiling of 23 is 30
The ceiling of 24 is 30
The ceiling of 25 is 30
The ceiling of 26 is 30
The ceiling of 27 is 30
The ceiling of 28 is 30
The ceiling of 29 is 30
The ceiling of 30 is 40
The ceiling of 31 is 40
The ceiling of 32 is 40
The ceiling of 33 is 40
The ceiling of 34 is 40
The ceiling of 35 is 40
The ceiling of 36 is 40
The ceiling of 37 is 40
The ceiling of 38 is 40
The ceiling of 39 is 40
The ceiling of 40 is 50
The ceiling of 41 is 50
The ceiling of 42 is 50
The ceiling of 43 is 50
The ceiling of 44 is 50
The ceiling of 45 is 50
The ceiling of 46 is 50
The ceiling of 47 is 50
The ceiling of 48 is 50
The ceiling of 49 is 50
The ceiling of 50 is 60
The ceiling of 51 is 60
The ceiling of 52 is 60
The ceiling of 53 is 60
The ceiling of 54 is 60
The ceiling of 55 is 60
The ceiling of 56 is 60
The ceiling of 57 is 60
The ceiling of 58 is 60
The ceiling of 59 is 60
The ceiling of 60 is 70
The ceiling of 61 is 70
The ceiling of 62 is 70
The ceiling of 63 is 70
The ceiling of 64 is 70
The ceiling of 65 is 70
The ceiling of 66 is 70
The ceiling of 67 is 70
The ceiling of 68 is 70
The ceiling of 69 is 70
The ceiling of 70 is 2147483647
The ceiling of 71 is 2147483647
The ceiling of 72 is 2147483647
The ceiling of 73 is 2147483647
The ceiling of 74 is 2147483647
The ceiling of 75 is 2147483647
The ceiling of 76 is 2147483647
The ceiling of 77 is 2147483647
The ceiling of 78 is 2147483647
The ceiling of 79 is 2147483647
The ceiling of 80 is 2147483647
The ceiling of 81 is 2147483647
The ceiling of 82 is 2147483647
The ceiling of 83 is 2147483647
The ceiling of 84 is 2147483647
The ceiling of 85 is 2147483647
The ceiling of 86 is 2147483647
The ceiling of 87 is 2147483647
The ceiling of 88 is 2147483647
The ceiling of 89 is 2147483647
The ceiling of 90 is 2147483647
The ceiling of 91 is 2147483647
The ceiling of 92 is 2147483647
The ceiling of 93 is 2147483647
The ceiling of 94 is 2147483647
The ceiling of 95 is 2147483647
The ceiling of 96 is 2147483647
The ceiling of 97 is 2147483647
The ceiling of 98 is 2147483647
The ceiling of 99 is 2147483647