CareerCup4.3.cpp

CareerCup4.3.cpp

/*
 * Chapter 4
 * 4.3 Given a sorted (increasing order) array with unique integer elements,
 * write an algorithm to create a binary search tree with minimal height.
 */

/* Recursive way to solve this problem */
#include <iostream>

using namespace std;

// Define tree_node struct
typedef struct tree_node {
    int value;
    struct tree_node* left;
    struct tree_node* right;
    tree_node(int value);
} tree_node;
// Constructor
tree_node::tree_node(int value) {
    this->value = value;
    left = NULL;
    right = NULL;
}

// Sorted array to BST
tree_node* buildBST(int a[], int start, int end)
{
    if (start > end)  // if start == end, means the first and last element is processing
        return NULL;  // Base case
    int mid = (end + start) / 2;  // Watch out: not (end - start) / 2
    tree_node* root = new tree_node(a[mid]);  // middle element must be root to ensure miminum height
    root->left = buildBST(a, start, mid - 1);  // recurse left part
    root->right = buildBST(a, mid + 1, end);  //recurse right part
    return root;
}

// Preorder print out BST
void preOrder(tree_node* root)
{
    if (root == NULL)
        return;
    cout << root->value << " ";
    preOrder(root->left);
    preOrder(root->right);
}

int main(int argc, char const *argv[])
{
    int a[5] = {1, 2, 3, 4, 5};
    tree_node* BST = buildBST(a, 0, 4);
    preOrder(BST);
    return 0;
}