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);
}
Comments