Tree

binary search tree, children on the left < x < children on right side
insertion and search complexity O(logN) delete is complicated.
illustration http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic9/

java code refer : http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic9/
c++ code refer: http://en.literateprograms.org/Binary_search_tree_(C)

One advantage balanced binary search trees have over hash tables is that they also retain a relative ordering among their contents. While the other operations aren't quite as fast as a hash table (refer to the table below), logarithmic time is certainly not bad by any means. However, if you're not interested in the ordering of its items or frequent iterating, a hash table is certainly the way to go.

### tree

#### preorder recrusive or not

``````public void iterativePreorder() {
BSTNode<E> p = root;
Stack<BSTNode<E>> stack = new Stack<BSTNode<E>>();
if (p != null) {
stack.push(p);

while (!stack.isEmpty()) {
p = (BSTNode<E>) stack.pop();
visit(p);
if (p.right != null)
stack.push(p.right);
if (p.left != null)
stack.push(p.left);
}
}
}```
```

#### inorder non recursive

```public void iterativeInorder() {
BSTNode<E> p = root;
Stack<BSTNode<E>> stack = new Stack<BSTNode<E>>();
while (p != null) {

while (p != null) {
if (p.right != null)    stack.push(p.right);
stack.push(p);
p = p.left;
}

p = (BSTNode<E>) stack.pop();
while (!stack.isEmpty() && p.right == null) {
visit(p);
p = (BSTNode<E>) stack.pop();
}
visit(p);
if (!stack.isEmpty()) {
p = (BSTNode<E>) stack.pop();
} else {
p = null;
}
}
}
```

#### iterative post order

approach -1

// left-to-right postorder = right-to-left preorder

``````public void iterativePostorder() {
IntBSTNode p = root;
Stack travStack = new Stack(); //trace用堆疊
output = new Stack(); //結果堆疊

if (p != null) { // left-to-right postorder = right-to-left preorder   LRV
travStack.push(p);

while (!travStack.isEmpty()) {
p = (IntBSTNode) travStack.pop();
output.push(p);

if (p.left != null) travStack.push(p.left);
if (p.right != null) travStack.push(p.right);
} //while

while (!output.isEmpty()) {
p = (IntBSTNode) output.pop();
p.visit();
}
} //if
}```
```

approach 2:

``````public void iterativePostorder() {
BSTNode<E> p = root, q = root;
Stack<BSTNode<E>> stack = new Stack<BSTNode<E>>();
while (p != null) {
while (p.left != null{
stack.push(p);
p = p.left;
}

while (p != null && (p.right == null || p.right == q)) {
visit(p);
q = p;
if (stack.isEmpty())
return;
p = (BSTNode<E>) stack.pop();
}
stack.push(p);
p = p.right;
}
}```
```

#### misc

• 一對中序順序(inorder sequence)及前序順序(preorder sequence)可唯一決定一個二元樹。
• 一對中序順序(inorder sequence)及後序順序(postorder sequence)亦可唯一決定一個二元樹。
• 一對前序順序(preorder sequence)及後序順序(postorder sequence)無法決定唯一一個二元樹

``````void Tree::LevelOrder()
{
Queue Q;
TreeNode *currentNode = root;
while (currentNode)
{
Visit(currentNode);
if (currentNode->leftChild)      Q.Push(currentNode->leftChild);
if (currentNode->rightChild)   Q.Push(currentNode->rightChild);
if (Q.IsEmpty())   return;
currentNode = Q.Pull();
}
}```
```

#### insert

```void BinarySearchTree::insert(int d)
{
tree_node* t = new tree_node;
tree_node* parent;

t->data = d;
t->left = NULL;
t->right = NULL;

parent = NULL;

// is this a new tree?
if(isEmpty()){
root = t;
}
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr = root;

while(curr)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}

if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
```
```struct node* insert(struct node* node, int data) {
// 1. If the tree is empty, return a new, single node
if (node == NULL) {
return(newNode(data));
}
else {
// 2. Otherwise, recur down the tree
if (data <= node->data) node->left = insert(node->left, data);
else node->right = insert(node->right, data);

return(node); // return the (unchanged) node pointer
}
}
```

#### delete

```Tree-Delete(T, z)
/* Determine which node to splice out: either z or z’s successor. */
if left[z] = NIL or right[z] = NIL
then y = z
else y = Tree-Successor[z]

/* Get x as descendant of y. */
if  left[y] != NIL
then x = left[y]
else x = right[y]

/* y is removed from the tree by manipulating pointers of  p[y] and x */
if x != NIL
then p[x] = p[y]

if p[y] = NIL
then root[T] = x
else if  y = left[p[i]]
then left[p[y]] = x
else right[p[y]] = x

/* copy y's data into z and delete y*/
if y != z
then  key[z] = key[y]
copy y’s data into z.

delete y;
```

other_versions

#### successor

```Tree-Successor(x)
1.  if right[x] != NIL
2.          then return Tree-Minimum(right[x])
3.     y = p[x]
4.     while y != NIL and x = right[y]
5.     do x = y
6.          y = p[y]
7.     return y
```

version-1 + 2 c code and splice code

#### min value

``````int minValue(struct node* node)
{
struct node* current = node;

while (current->left != NULL)
{
current = current->left;
}

return(current->data);
}```
```

#### Write C code to check if a given binary tree is a binary search tree or not?

``````int isThisABST(struct node* mynode)
{
if (mynode==NULL) return(true);
if (node->left!=NULL && maxValue(mynode->left) > mynode->data)
return(false);
if (node->right!=NULL && minValue(mynode->right) <= mynode->data)
return(false);
if (!isThisABST(node->left) || !isThisABST(node->right))
return(false);

return(true);
}```
```

#### deepest common ancestor

Find the deepest common ancestor of two leaves in a binary search tree;
Do not traverse from the leaves. Instead, locate the node top/down.
How about finding the shallowest common ancestor of two leaves?

```void deepest(node * x)
{
if(x==null) return;

push_into_queue(x);

if(x.value> p.value && x.value < q.value)
return;
if(x.value> q.value)
deepest(x->left);
if(x.value< p.value)
deepest(x->right);
}
```

#### convert a binary tree into a linked list

```struct Tree
{
int i;
struct Tree* left;
struct Tree* right;
};
Tree * Convert_to_list (Tree* T)
{
Tree * T1, T2, temp;
if (T != NULL)
{
T1 = Convert_to_list(T->left)
T2 = Convert_to_list(T->right)
T->right = T2;
if (T1!= NULL)
{
temp = T1;
while (temp->right)
temp = temp->right;
temp->right = T;
return T1;
}
else
return T;
}
else
return NULL;
}
```

##### insert
``````public void threadedInsert(int el) {
If (root == null) {    // tree is empty
root = newNode;
return;}
IntThreadedNode p = root, prev = null;
while (p != null) {    // find a place to insert newNode;
prev = p;
if (el < p.key)
p = p.left;
else if (!p.Successor)     // go to the right only if it is
p = p.right;    // a descendant, not a successor;
else break;     // don't follow successor link;
}
if (el < prev.key) {    // if newNode is left child of
prev.left = newNode;    // its parent, the parent
newNode.Successor = true;// also becomes its successor;
newNode.right = prev;   }
else if (prev.Successor) {    // if parent of the newNode
newNode.Successor = true;// is not the rightmost node,
prev.Successor = false;    // make parent's successor
newNode.right = prev.right;    // newNode’s successor,
prev.right = newNode;}
else prev.right = newNode;    // otherwise it has no successory;
} //```
```
##### inorder
``````protected void threadedInorder( ) {
IntThreadedNode prev, p = root;

if (p != null) {    //process only nonempty trees;
while (p.left != null)    // go to the leftmost node;
p = p.left;

while (p !=null) {
p.visit( );
prev = p;
p = p.right;    //go to the right node

if (p != null && !prev.successor) // if it is a descendant,go to the leftmost node,
while (p.left != null)    p = p.left;
}// while (p !=null)
} // if
}```
```