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