Binary Search Tree

1. Data structure organized as trees will prove valuable for a range of applications, especially for problems of information retrieval.
2. A binary tree is either empty,ot it consists of one node called root together with two binary trees called left subtree and the right subtree of the root.
3. Three ways to traverse the binary tree: (1) preorder: (root, left, right) (2)Inorder: (left, root, right) (3) postorder: (left, right, root)
4. Express Tree: An expression tree is built up from the simple operands and operators of an expression by placing the simple operands as the leaves of a binary tree and the operators as interior nodes.
5. The binary tree is used to implement the binary search tree and binary heap.
6. The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero.
7. The size of a node is the number of descendants it has including itself.
8. The Binary Search Tree (BST): the BST is a binary tree with the following property, any node in the tree, is greater than any nodes in its left tree and less or equal to every item in its right subtree.
9. An inorder traverse of the BST will process the items in increasing order.
10. The insertion and searching are efficient with BST, provided that the BST is close to being ballanced. A binary tree is called balanced if for any node in the tree, the number of nodes in its left subtree is approximately same as in its right subtree.
11. When inserting a new node into BST we always insert the new node as a leaf node.
12. The nodes' values in BST must be unique, doesn't allow to insert a duplicate node.
13. For any BST, the smallest value is at the left-most node, the biggest value is at the right-most node.

template
int binaryTree::size()
//return the number of nodes in the binay tree
{
int count =0;
recursiveSize(root, count);
return count;
}
template
void binaryTree::recursiveSize(treeNode* subTree, int& count)
//use recursive method to get the num of nodes in the binary tree
//traverse the tree in pre-order
{
if(subTree != NULL) {
count++;
recursiveSize(subTree->left, count);
recursiveSize(subTree-right, count);
}
}

template
int binaryTree::height()
//return -1 if the tree is empty, return 1 if the tree is root tree
{
int height;
if(root == NULL)
return -1;
recursiveHeight(root, height);
return height;
}

template
void binaryTree::recursiveHeight(treeNode* subTree, int& height)
//get the heights for the left and right subtree, then add 1 to the max of them
{
int lh, rh;
if( subTree == NULL) {
height = -1;
}
else {
recursiveHeight(subTree->left, lh);
recursiveHeight(subTree->right, rh);
height = ( (lh > rh)?lh:rh ) + 1;
}
}


TreeNode* TreeNode::clone()
{
if (TreeNode* tmp = new TreeNode)
{
tmp->ascii = ascii;
if (left) tmp->left = left->clone();
if (right) tmp->right = right->clone();
return tmp;
}
return 0;
}