write a method to generate a perfectly binary search tree of

write a method to generate a perfectly binary search tree of height h with keys 1 through 2h+1-1 what is the running time of your method

Solution

// method to generate a perfectly binary search tree of height h with keys 1 through 2h+1-1

public BSTreeNode recursiveGenerateTree (int h)
{
return generateTree (1, Math.pow(2, h + 1) - 1);
}

private BSTreeNode recursiveGenerateTree (int start, int end)
{
// base case start = end
if (start == end)
return new BSTreeNode(start, null, null);
  
// set root
int root = (start + end) / 2;

// recursively call left and right subtree
BSTreeNode l = recursiveGenerateTree (start, root - 1);
BSTreeNode r = recursiveGenerateTree (root + 1, end);
  
return new BSTreeNode(root, l, r);
}

Running time: O(2^h )
h: height of tree.