I was doing an exercise to convert a sorted array to a binary search tree where every node in the tree has its children whose heights at most differ by 1.
One simple solution is to pick out the middle element to be the root. Middle as in (0+size) integer divided by 2 and then make the left, right children by a recursive call on the left half, right half of the remaining array respectively.
And one can check that the solution works via some testing. (Example code in C++ attached at the end.)
However, I am having trouble proving why this solution works.
Why?
I tried reasoning inductively: for any node with height K>3, assume all height k<K nodes are 1) height balanced, and 2) if k−2≥0, then the max possible size of k−2 height nodes + 1 is less than the min size of height k nodes
Since max size is strictly increasing on height, (2) means if height difference ≥2 then the size difference is ≥2.
It's easy enough to prove that any node with height K is height balanced with the inductive assumption. But I am having trouble proving part (2) for K.
Below is a size chart and it also has the base case.
| height | min size | max size |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 3 |
| 3 | 4 | 7 |
| 4 | 7 | 15 |
The min and max sizes have the following recurrence relations:
min size of height K nodes = 1 + min size of height K−1 nodes + the min size of height K−2 nodes = Fib(n)+n *
max size of height K node = max size of K−1 node x 2 + 1 =2^(n-1) − 1
* last equal sign is "probably"
Fib(n)+n seems greater than 2^(n-1), especially with the rounding relation shown on its Wikipedia page. But then I'd be left with proving this rather involved inequality, going through the rounding relation and such.
Is there something simple that I am missing?
Is there an easier way to prove the correctness of the solution altogether?
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void deleteTree(TreeNode* root) {
if (root) {
if (root->left) {
deleteTree(root->left);
}
if (root->right) {
deleteTree(root->right);
}
delete root;
}
}
// one can print the tree to Graphviz script for example for inspection; my code for that has a lot of other things together so I'll skip that
// technically meant to be a different file below
#include<vector>
#include<iostream>
#define DEBUG
TreeNode* sortedArrayToBST(std::vector<int>& nums, std::size_t i, std::size_t j) {
#ifdef DEBUG
std::cout << "i = " << i << "\tj = " << j << '\n';
#endif // DEBUG
if (i >= j) {
return nullptr;
}
else {
std::size_t k{ (i + j) / 2 };
#ifdef DEBUG
std::cout << "\tk = " << k << '\n';
#endif // DEBUG
TreeNode* node{ new TreeNode(nums[k]) };
node->left = sortedArrayToBST(nums, i, k);
node->right = sortedArrayToBST(nums, k+1, j);
return node;
}
}
TreeNode* sortedArrayToBST(std::vector<int>& nums) {
return sortedArrayToBST(nums, 0, nums.size());
}
int main() {
std::vector<int> q1{ -4, -3, 0, 1, 2 };
TreeNode* node{ sortedArrayToBST(q1) };
deleteTree(node);
}
