Binary Search Tree

Binary Search Tree: for each node, all elements in its left tree are less than or equal to (<=) the node, and all the elements in its right tree are larger than the node. A binary search tree is different from a binary tree.

Binary Search Tree is good at insert and lookup. On average, binary tree will locate a node in O(logn) time. BST is a good way to practice recursion.

Typical operations on BST:
1. Search
2. Delete min value
3. Delete max value
4. Remove node
We need to consider several cases: 1) leaf node, simply delete it 2) node with only one child, then we delete the node and bypass its parent pointer to the node's child 3) node with two children. We first need to find the min node in the node's right tree, replace the node with this min value and then remove the min node.
5. Delete BST
You can implement this with an elegant recursive function.


struct node
{
int data;
struct node * left;
struct node * right;
}

Lookup()

BST Checking: Check every node to see whether it meets the BST definition.

*****
Q1: Print each path from root to leaf

void PrintArr(int path[], int pathLen)
{
int i;
for(i=0;idata;
pathLen++;
}

if(node->left == NULL && node->right == NULL)
PrintArr(path, pathLen);
else
{
RecurPrintPath(node->left, path, pathLen);
RecurPrintPath(node->right, path, pathLen);
}
}

void PrintPaths(struct node * node)
{
int path[1000];

RecurPrintPath(node, path, 0);
}

NOTE: A good recursion with a helper function. Watch how path and pathLen changes and the according values in different recursion level.

Q2: Print a binary tree level by level. Top down or Bottom up. How about one level per line for the output?

The top down idea is similar to breadth-first search (BFS) using QUEUE data structure. The bottom up idea can be achieved by recursively print the top down method or we can use a stack to simulate this procedure.

code snippet:

Top-Down

while(!Q.empty())
{
printf("%d ", Q.front()->data);
if(Q.front()->left!=NULL)
Q.push(Q.front()->left);
if(Q.front()->right!=NULL)
Q.push(Q.front()->right);
Q.pop();
}

Bottom-up

while(!Q.empty())
{
//printf("%d ", Q.front()->data);
S.push(Q.front());
if(Q.front()->right!=NULL)
Q.push(Q.front()->right);
if(Q.front()->left!=NULL)
Q.push(Q.front()->left);
Q.pop();
}

while(!S.empty())
{
printf("%d ", S.top()->data);
S.pop();
}
----------------Recursive Version-------------------

void PrintLevelRecur(queue <.struct node *.> Q)
{
if(Q.empty())
return;

struct node * tmp = NULL;

if(Q.front()->left!=NULL)
Q.push(Q.front()->left);
if(Q.front()->right!=NULL)
Q.push(Q.front()->right);

tmp = Q.front();
Q.pop();

PrintLevelRecur(Q);

printf("%d ", tmp->data);


}
void PrintLevelbyLevel(struct node * node) //wrapper function
{
queue<.struct node *.> Q;

if(node!=NULL)
Q.push(node);

PrintLevelRecur(Q);
}