### Implement a binary tree

Implement a binary tree and solve the following:
1) Write a function to find the immediate common ancestor of any two nodes in the tree
2)  Print elements in pre-order, in-order and post-order traversals
3)  Check if a binary tree is a Binary Search Tree
`/*`
` * BinaryTreeNode.cpp`
` *`
` *  Created on: Apr 21, 2012`
` *      Author: Kiran Hegde`
` */`

`#include <iostream>`
`#include <algorithm>`
`#include <queue>`
`#include <string>`
`#include <list>`
`#include <limits>`

`using namespace std;`

`class BinaryTreeNode {`
`public :`
`    BinaryTreeNode(int d) : left(NULL), right(NULL), data(d) {}`

`    ~BinaryTreeNode() {`
`        if (left != NULL) {`
`            delete left;`
`            left = NULL;`
`        }`
`        if (right != NULL) {`
`            delete right;`
`            right = NULL;`
`        }`
`    }`

`    //Method to insert data to create a binary search tree (i.e. left <= node < right)`
`    void insert(int x) {`
`        if (x < data) {`
`            if (left != NULL)`
`                left->insert(x);`
`            else {`
`                BinaryTreeNode *node = new BinaryTreeNode(x);`
`                left = node;`
`            }`
`        }`
`        else {`
`            if (right != NULL)`
`                right->insert(x);`
`            else {`
`                BinaryTreeNode *node = new BinaryTreeNode(x);`
`                right = node;`
`            }`
`        }`
`    }`

`    //Method to find d if this is a binary search tree`
`    BinaryTreeNode *find(int d) {`
`        if (d == data) {`
`            return this;`
`        }`
`        else {`
`            if (d < data) {`
`                return (left != NULL ? left->find(d) : NULL);`
`            }`
`            else if (d > data){`
`                return (right != NULL ? right->find(d) : NULL);`
`            }`
`        }`
`        return NULL;`
`    }`

`    int height() {`
`        int heightLeft = (left == NULL ? 0: left->height());`
`        int heightRight = (right == NULL ? 0: right->height());`
`        int height = 1 + max(heightLeft, heightRight);`
`        return height;`
`    }`

`    BinaryTreeNode *left;`
`    BinaryTreeNode *right;`
`    int data;`

`};`

`/**`
` * Create a Binary Tree from any array.  The tree is created such that beginning`
` * of the array is mapped to the root of the tree and subsequent array elements`
` * are added as the children, going from left to right and top to bottom`
` */`
`BinaryTreeNode *createBinaryTreeFromArray(int *array, int size) {`
`    if (array == NULL) {`
`        return NULL;`
`    }`
`    queue<BinaryTreeNode *> myQueue;`
`    BinaryTreeNode *root = new BinaryTreeNode(array[0]);`
`    myQueue.push(root);`
`    bool done = false;`
`    int i = 1;`
`    while (!done) {`
`        BinaryTreeNode *node = myQueue.front();`
`        if (node->left == NULL) {`
`            node->left = new BinaryTreeNode(array[i]);`
`            myQueue.push(node->left);`
`            i++;`
`        }`
`        else if (node->right == NULL) {`
`            node->right = new BinaryTreeNode(array[i]);`
`            myQueue.push(node->right);`
`            i++;`
`        }`
`        else {`
`            myQueue.pop();`
`        }`
`        if (i == size)`
`            done = true;`
`    }`
`    return root;`
`}`

`/**`
` * Recursive function to create a binary search tree from sorted array`
` */`
`BinaryTreeNode *createMinimalBST(int *array, int start, int end, int level) {`
`    if (end < start) {`
`        return NULL;`
`    }`
`    int mid = (start + end)/2;`
`    BinaryTreeNode *node = new BinaryTreeNode(array[mid]);`
`    node->left = createMinimalBST(array, start, mid-1, level + 1);`
`    node->right = createMinimalBST(array, mid+1, end, level + 1);`
`    return node;`
`}`

`/**`
` * Create a minimal Binary Search Tree from any array`
` */`
`BinaryTreeNode *createMinimalBSTFromArray(int *array, int size) {`
`    //First sort the array`
`    list<int> dataList;`
`    for (int i=0; i<size; i++) {`
`        dataList.push_back(array[i]);`
`    }`
`    dataList.sort();`
`    list<int>::iterator it;`
`    int i=0;`
`    for (it=dataList.begin(); it != dataList.end(); it++) {`
`        array[i++] = *it;`
`    }`

`    BinaryTreeNode *root = createMinimalBST(array, 0, size-1, 0);`
`    return root;`
`}`

`void printTree(BinaryTreeNode *root) {`
`    if (root == NULL){`
`        return;`
`    }`
`    queue<BinaryTreeNode *> treeQueue;`
`    queue<int> levelQueue;`
`    queue<int> parentQueue;`
`    queue<string> rightLeftFlagQueue;`

`    treeQueue.push(root);`
`    levelQueue.push(0);`
`    parentQueue.push(root->data);`
`    rightLeftFlagQueue.push("Top");`

`    cout << "Level 1: ";`

`    int prevLevel = 0;`
`    while(! treeQueue.empty()) {`
`        BinaryTreeNode *node = treeQueue.front();`
`        int level = levelQueue.front();`
`        if (node != NULL) {`
`            if (level > prevLevel) {`
`                prevLevel = level;`
`                cout << endl;`
`                cout << "Level " << level + 1 << ": ";`
`            }`
`            int parentData = parentQueue.front();`
`            string rightLeftFlag = rightLeftFlagQueue.front();`
`            if (level > 0) {`
`                cout << parentData << "-->" ;`
`            }`
`            cout << node->data << " ";`
`            if (level > 0) {`
`                cout << rightLeftFlag << "  ";`
`            }`
`            if (node->left != NULL) {`
`                treeQueue.push(node->left);`
`                levelQueue.push(level + 1);`
`                parentQueue.push(node->data);`
`                rightLeftFlagQueue.push("L");`
`            }`
`            if (node->right != NULL) {`
`                treeQueue.push(node->right);`
`                levelQueue.push(level + 1);`
`                parentQueue.push(node->data);`
`                rightLeftFlagQueue.push("R");`
`            }`
`        }`
`        treeQueue.pop();`
`        levelQueue.pop();`
`        parentQueue.pop();`
`        rightLeftFlagQueue.pop();`
`    }`
`}`

`void preOrderTraversal(BinaryTreeNode *root) {`
`    if (root == NULL)`
`        return;`
`    cout << root->data << " ";`
`    preOrderTraversal(root->left);`
`    preOrderTraversal(root->right);`
`}`

`void inOrderTraversal(BinaryTreeNode *root) {`
`    if (root == NULL)`
`        return;`
`    inOrderTraversal(root->left);`
`    cout << root->data << " ";`
`    inOrderTraversal(root->right);`
`}`

`void postOrderTraversal(BinaryTreeNode *root) {`
`    if (root == NULL)`
`        return;`
`    postOrderTraversal(root->left);`
`    postOrderTraversal(root->right);`
`    cout << root->data << " ";`
`}`

`bool isParent(BinaryTreeNode *node1, BinaryTreeNode *node2) {`
`    if (node1 == NULL)`
`        return false;`
`    if (node1 == node2)`
`        return true;`
`    return (isParent(node1->left, node2) || isParent(node1->right, node2));`
`}`

`/**`
` * Find the closest ancestor (if any) that is common to both node1 and node2`
` * in a binary tree represented by ancestor.`
` */`
`BinaryTreeNode *findCommonAncestor(BinaryTreeNode *ancestor, BinaryTreeNode *node1,`
`        BinaryTreeNode *node2) {`
`    if (ancestor == NULL) {`
`        return NULL;`
`    }`
`    bool isNode1OnLeft = isParent(ancestor->left, node1);`
`    bool isNode2OnLeft = isParent(ancestor->left, node2);`
`    if (isNode1OnLeft != isNode2OnLeft)`
`        return ancestor;`
`    else {`
`        if (isNode1OnLeft)`
`            return findCommonAncestor(ancestor->left, node1, node2);`
`        else`
`            return findCommonAncestor(ancestor->right, node1, node2);`
`    }`
`}`

`/**`
` * Helper to check whether BST`
` */`
`bool checkIfBST(BinaryTreeNode *root, int leftVal, int rightVal) {`
`    if (root == NULL)`
`        return true;`
`    if ((root->data > rightVal) || (root->data < leftVal))`
`        return false;`
`    return (checkIfBST(root->left, leftVal, root->data) &&`
`            checkIfBST(root->right, root->data, rightVal));`
`}`

`/**`
` * Check if a binary tree is a binary search tree (BST)`
` */`
`bool checkIfBST(BinaryTreeNode *root) {`
`    return checkIfBST(root, numeric_limits<int>::min(), numeric_limits<int>::max());`
`}`

`/**`
` * Test the code`
` */`
`int main() {`
`    int treeArray[] = { 9, 13, 14, 15, 16, 17, 1, 2, 10, 11, 12, 3, 4, 5, 6, 7, 8};`

`    cout << "Array: " << endl;`
`    for (int i=0; i<17; i++) {`
`        cout << treeArray[i] << " ";`
`    }`
`    cout << endl << endl;`

`    //Binary tree created from array with each element`
`    BinaryTreeNode *root = createBinaryTreeFromArray(treeArray, 17);`
`    cout << "Binary Tree from array: height = " << root->height() << endl;`
`    printTree(root);`
`    cout << endl << "Found '10' in tree: " <<`
`            (root->find(10) != NULL?"Yes":"No") << endl;`

`    cout << "BST? " << (checkIfBST(root)?"Yes":"No") << endl;`

`    //Pre-Order, In-Order and Post-Order Traversal`
`    cout << endl << "Pre Order Traversal: " << endl;`
`    preOrderTraversal(root);`
`    cout << endl << endl;`

`    cout << "In Order Traversal: " << endl;`
`    inOrderTraversal(root);`
`    cout << endl << endl;`

`    cout << "Post Order Traversal: " << endl;`
`    postOrderTraversal(root);`
`    cout << endl << endl;`

`    //Create a Binary Search Tree from the same array`
`    BinaryTreeNode *rootBST = new BinaryTreeNode(treeArray[0]);`
`    for (int i=1; i<17; i++) {`
`        rootBST->insert(treeArray[i]);`
`    }`
`    cout << endl << "Binary Search Tree from array: height = "`
`            << rootBST->height() << endl;`
`    printTree(rootBST);`
`    cout << endl << "Found '10' in tree: " <<`
`            (rootBST->find(10)!= NULL?"Yes":"No") << endl;`

`    cout << "BST? " << (checkIfBST(rootBST)?"Yes":"No") << endl;`

`    //Create a minimal Binary Search Tree from the same array`
`    BinaryTreeNode *rootMinBST = createMinimalBSTFromArray(treeArray, 17);`
`    cout << endl << endl << "Minimum Binary Search Tree from array: height = "`
`            << rootMinBST->height() << endl;`
`    printTree(rootMinBST);`
`    cout << endl << "Found '10' in tree: " <<`
`            (rootMinBST->find(10)!= NULL?"Yes":"No") << endl;`

`    cout << "BST? " << (checkIfBST(rootMinBST)?"Yes":"No") << endl;`

`    BinaryTreeNode *n1 = rootMinBST->find(10);`
`    BinaryTreeNode *n2 = rootMinBST->find(17);`
`    BinaryTreeNode *res = findCommonAncestor(rootMinBST, n1, n2);`
`    cout << endl << "The closest ancestor to " << n1->data << " and " << n2->data`
`            << " is " << res->data << endl;`

`    delete(root);`
`    delete(rootBST);`
`    delete(rootMinBST);`
`}`