## 1 BST Class

A binary search tree is a kind of binary tree. Each node of it contains its key, satellite data, attributes left, right, p that point to its left child, right child, and parent. It satisfies the following binary-search-tree property: Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key<=x.key. If y is a node in the right subtree of x, then y.key>=x.key.


class TreeNode
{
public:
int key;
TreeNode* left;
TreeNode* right;
TreeNode* p;
TreeNode (int k);//Constructor to create a treenode with a key k
TreeNode (const TreeNode* r); //Constructor to copy other treenode
// In this experiment, we just ingore the satellite data.
};

class BST
{
public:
TreeNode * root;
};



## 2 Create and Print BST

BST is different from ordinary binary tree. The treenodes should satisfy the BST property. So the treenodes should be inserts to the BST one by one to satisfy the property at each step. So first we discuss how to insert a treenode.

Obviously, we can insert all new treenodes to the leaves because of the BST property.

void TreeInsert(BST* T, TreeNode* z)
{
TreeNode* y = NULL;
TreeNode* x = T->root;
while (x != NULL)
{
y = x;
if (z->key < x->key)
{
x = x->left;
}
else
{
x = x->right;
}
}
z->p = y;
if (y == NULL)
{
T->root=z;
}
else if (z->key < y->key)
{
y->left = z;
}
else
{
y->right = z;
}
}


Then we could create a BST by TreeInsert function. We will know one fact from the codes before and then, the basic operations of BST runs in $$O(h)$$, where h is the height of BST. And we can prove that if the treenodes are randomly inserted to the BST, the expected height of BST on n distinct keys is $$O(lgn)$$. We know \left \lfloor lgn \rfloor \right is the lowest height of BST. So we could randomly build BST to improve the time complexity of BST basic operations.

In this experiment, the treenodes’ keys are stored in an array.

BST* TreeRandomizedInit(vector<int> key)
{
random_shuffle(key.begin(), key.end());
BST*T=new BST();
for (int i = 0; i < key.size(); i++)
{
TreeInsert(T, new TreeNode(key[i]));
}
return T;
}


When a BST is created, we want to see the structure of it. So we need to print the BST. In order to clearly see the structure, we should use implement BFS (Breadth First Search) to the BST. When we print treenodes of one layer, we could push the layer’s treenodes to a queue. And when we print next layer, we just pop the treenodes from the queue and do the same thing to their leftchild and rightchild. If a treenode is null, then print “#” to show it.

void BFSPrint(BST* T)
{
TreeNode* x = T->root;
queue<TreeNode*> q;
q.push(x);
int qs;
TreeNode* tmp;
int exist = 0;
while (true)
{
exist = 0;
qs = q.size();
for (int i = 0; i < qs; i++) { tmp = q.front(); q.pop(); if (tmp == NULL) { printf("# "); q.push(NULL); q.push(NULL); } else { printf("%d ", tmp->key);
exist = 1;
if (tmp->left!= NULL)
{
q.push(tmp->left);
}
else
{
q.push(NULL);
}
if (tmp->right != NULL)
{
q.push(tmp->right);
}
else
{
q.push(NULL);
}
}
}
printf("\n");
if (exist == 0)
{
break;
}

}
}


## 3 Tree Walk(Treversal)

Tree walk (Treversal) is a process of visiting the treenodes of a tree. Generally, there are following visiting sequences of three ways of tree walk.

Inorder tree walk: left subtree, root, right subtree

Preorder tree walk: root, left subtree, right subtree

Postorder tree walk: left subtree, right subtree, root

The recursive method to implement them is easy to understand.

void InorderTreeWalk(TreeNode* x)
{
if (x != NULL)
{
InorderTreeWalk(x->left);
printf("%d ", x->key);
InorderTreeWalk(x->right);
}
}

void PreorderTreeWalk(TreeNode* x)
{
if (x != NULL)
{
printf("%d ", x->key);
PreorderTreeWalk(x->left);
PreorderTreeWalk(x->right);
}
}

void PostorderTreeWalk(TreeNode* x)
{
if (x != NULL)
{
PostorderTreeWalk(x->left);
PostorderTreeWalk(x->right);
printf("%d ", x->key);
}
}


However, we often discuss the nonrecursive methods of traversal. A easier way is to use stack to store the treenodes.

Inorder tree walk and preorder tree walk are easy to understand. Their difference is that inorder tree walk is visiting one treenode after poping it from the stack while preorder tree walk is visiting one treenode before pushing it to the stack.

void InorderTreeWalk_stack(TreeNode* x)
{
stack<TreeNode*> s;
while (s.size() > 0 || x != NULL)
{
if (x == NULL)
{
x = s.top();
s.pop();
printf("%d ", x->key);
x = x->right;
}
else
{
s.push(x);
x = x->left;
}
}
s.~stack();
}

void PreorderTreeWalk_stack(TreeNode* x)
{
stack<TreeNode*> s;
while (s.size() > 0 || x != NULL)
{
if (x == NULL)
{
x = s.top();
s.pop();
x = x->right;
}
else
{
printf("%d ", x->key);
s.push(x);
x = x->left;
}
}
s.~stack();
}


But the postorder tree walk in a nonrecursive way is trivial.

One method is to use two stacks. First modify the preorder tree walk from root-left-right to root-right-left sequence to get reverse postorder tree walk. And then reverse the postorder tree walk.

void PostorderTreeWalk_twostack(TreeNode* x)
{
stack<TreeNode*> s1;
stack<TreeNode*> s2;
while (s1.size() > 0 || x != NULL)
{
if (x == NULL)
{
x = s1.top();
s1.pop();
x = x->left;
}
else
{
s2.push(x);
s1.push(x);
x = x->right;
}
}
while (s2.size() > 0)
{
x = s2.top();
printf("%d ", x->key);
s2.pop();
}
s1.~stack();
s2.~stack();
}


And we can also use one stack to implement it. First move down to the leftmost treenode. Push the root and root’s right child to stack while moving down. Then pop the stack. If the treenode poped does not have a right child, print it and set it null. If the treenode poped has a right child and the right child is at the top of the stack, pop the right child from the stack, push the root back and set root as root’s right child. When the stack is empty, break the loop. The operations of judging right child aims to satisfy the rule that right is before root.

void PostorderTreeWalk_stack(TreeNode* x)
{
stack<TreeNode*> s;
TreeNode* p;
while (s.size() > 0 || x != NULL)
{
if (x == NULL)
{
x = s.top();
s.pop();
if (x->right != NULL&&s.size()>0&&s.top()==x->right)
{
p = s.top();
s.pop();
s.push(x);
x = x->right;
}
else
{
printf("%d ", x->key);
x = NULL;
}
}
else
{
if(x->right!=NULL)
s.push(x->right);
s.push(x);
x = x->left;
}
}
s.~stack();
}


## 4 Find

BST search can be implemented in recursive way and nonrecursive way. They are easy to understand.

TreeNode* TreeSearch(TreeNode* x, int k)
{
if (x == NULL || k == x->key)
{
return x;
}
if (k < x->key)
{
return TreeSearch(x->left, k);
}
else
return TreeSearch(x->right, k);
}

TreeNode* IterativeTreeSearch(TreeNode* x, int k)
{
while (x != NULL && k != x->key)
{
if (k < x->key)
{
x = x->left;
}
else
x = x->right;
}
return x;
}


Then finding the maximum and minimum are obvious.

TreeNode* TreeMinimum(TreeNode* x)
{
while (x->left != NULL)
{
x = x->left;
}
return x;
}

TreeNode* TreeMaximum(TreeNode* x)
{
while (x->right != NULL)
{
x = x->right;
}
return x;
}


And finding the inorder successor and inorder predecessor are just considering both the child and the parent.

TreeNode* Successor(TreeNode* x)
{
if (x->right != NULL)
{
return TreeMinimum(x->right);
}
TreeNode* y = x->p;
while (y != NULL && x == y->right)
{
x = y;
y = y->p;
}
return y;
}

TreeNode* Predecessor(TreeNode* x)
{
if (x->left != NULL)
{
return TreeMaximum(x->left);
}
TreeNode* y = x->p;
while (y != NULL && x == y->left)
{
x = y;
y = y->p;
}
return y;
}


## 5 Delete

The process of deleting has four cases. They are clear in the image.

In  these processes, treenodes need to be transplanted. So first implement the transplant function.

void Transplant(BST* T, TreeNode* u, TreeNode* v)
{
if (u->p == NULL)
{
T->root = v;
}
else if (u == u->p->left)
{
u->p->left = v;
}
else
{
u->p->right - v;
}
if (v != NULL)
{
v->p = u->p;
}
}


Then implement the deleting function.

void TreeDelete(BST* T, TreeNode* z)
{
if (z->left == NULL)
{
Transplant(T, z, z->right);
}
else if(z->right == NULL)
{
Transplant(T, z, z->left);
}
else
{
TreeNode* y = TreeMinimum(z->right);
if (y->p != z)
{
Transplant(T, y, y->right);
y->right = z->right;
y->right->p = y;
}
Transplant(T, z, y);
y->left = z->left;
y->left->p = y;
}
}


## 6 Test

Test codes:

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
TreeNode* tmpnode;
BST* tmptree=new BST();
int k;
while (scanf("%d", &n) != EOF)
{
vector<int> key(n);
for (int i = 0; i < n; i++) scanf("%d", &key[i]); BST*T=TreeRandomizedInit(key); BFSPrint(T); printf("Recursive InorderTreeWalk:\n"); InorderTreeWalk(T->root);
printf("\n");
printf("Nonrecursive InorderTreeWalk:\n");
InorderTreeWalk_stack(T->root);
printf("\n");
printf("Recursive PreorderTreeWalk:\n");
PreorderTreeWalk(T->root);
printf("\n");
printf("Nonrecursive PreorderTreeWalk:\n");
PreorderTreeWalk_stack(T->root);
printf("\n");
printf("Recursive PostorderTreeWalk:\n");
PostorderTreeWalk(T->root);
printf("\n");
printf("Nonrecursive PostorderTreeWalk with two stacks:\n");
PostorderTreeWalk_twostack(T->root);
printf("\n");
printf("Nonrecursive PostorderTreeWalk with one stack:\n");
PostorderTreeWalk_stack(T->root);
printf("\n");
printf("TreeSearch:");
scanf("%d", &k);
tmpnode=TreeSearch(T->root, k);
tmptree->root = tmpnode;
BFSPrint(tmptree);
printf("IterativeTreeSearch:");
scanf("%d", &k);
tmpnode = IterativeTreeSearch(T->root, k);
tmptree->root = tmpnode;
BFSPrint(tmptree);
printf("TreeMaximum:\n");
tmpnode = TreeMaximum(T->root);
tmptree->root = tmpnode;
BFSPrint(tmptree);
printf("TreeMinimum:\n");
tmpnode = TreeMinimum(T->root);
tmptree->root = tmpnode;
BFSPrint(tmptree);
printf("Inorder Successor:\n");
tmpnode = Successor(T->root);
tmptree->root = tmpnode;
BFSPrint(tmptree);
printf("Inorder Predecessor:\n");
tmpnode = Predecessor(T->root);
tmptree->root = tmpnode;
BFSPrint(tmptree);
printf("Delete one treenode of exact key:");
scanf("%d", &k);
TreeDelete(T, IterativeTreeSearch(T->root,k));
BFSPrint(T);
}
return 0;
}


Test case and result:

11
15 6 18 3 7 17 20 2 4 13 9
9
6 13
2 7 # 18
# 3 # # # # 15 20
# # # 4 # # # # # # # # # 17 # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
Recursive InorderTreeWalk:
2 3 4 6 7 9 13 15 17 18 20
Nonrecursive InorderTreeWalk:
2 3 4 6 7 9 13 15 17 18 20
Recursive PreorderTreeWalk:
9 6 2 3 4 7 13 18 15 17 20
Nonrecursive PreorderTreeWalk:
9 6 2 3 4 7 13 18 15 17 20
Recursive PostorderTreeWalk:
4 3 2 7 6 17 15 20 18 13 9
Nonrecursive PostorderTreeWalk with two stacks:
4 3 2 7 6 17 15 20 18 13 9
Nonrecursive PostorderTreeWalk with one stack:
4 3 2 7 6 17 15 20 18 13 9
TreeSearch:6
6
2 7
# 3 # #
# # # 4 # # # #
# # # # # # # # # # # # # # # #
IterativeTreeSearch:6
6
2 7
# 3 # #
# # # 4 # # # #
# # # # # # # # # # # # # # # #
TreeMaximum:
20
# #
TreeMinimum:
2
# 3
# # # 4
# # # # # # # #
Inorder Successor:
13
# 18
# # 15 20
# # # # # 17 # #
# # # # # # # # # # # # # # # #
Inorder Predecessor:
7
# #
Delete one treenode of exact key:6
9
7 13
2 # # 18
# 3 # # # # 15 20
# # # 4 # # # # # # # # # 17 # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #


### Reference

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.