tree1.h fully updated

//We will do following Functions:
1. lookup
2. Insert
3. printTree,printPost, printPre
4. Selection Function
5. Delete(Hence implemented - child0,child1,child2, inorder2 functions)

#ifndef TREE1_H
#define TREE1_H
# include <stdio.h>
# include <stdlib.h>
#define isChildless(p) p->left==NULL &&p->right==NULL
enum BOOL{false,true} ;
typedef enum BOOL BOOL;
struct node {
 int data;
 struct node* left;
 struct node* right;
} ;
typedef struct node node;
/*
Given a binary tree, return true if a node
with the target data is found in the tree. Recurs
down the tree, chooses the left or right
branch by comparing the target to each node.
 */
static int lookup(node* node, int target) {
 // 1. Base case == empty tree
 // in that case, the target is not found so return false
 if (node == NULL) {
  return(false);
 }
 else {
  // 2. see if found here
  if (target == node->data) return(true);
  else {
   // 3. otherwise recur down the correct subtree
   if (target <>data) return(lookup(node->left, target));
   else return(lookup(node->right, target));
  }
 }
}
node* newNode(int data) {
 node* temp = (node*) malloc(sizeof(node)); // "new" is like "malloc"
 temp->data = data;
 temp->left = NULL;
 temp->right = NULL;
 return(temp);
}
/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree.
Returns the new root pointer which the caller should
then use (the standard trick to avoid using reference
parameters).
 */
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
 }
}
//functions simply on traversals
int size(node *p)
{
 if (p==NULL) {
  return(0);
 } else {
  return(size(p->left) + 1 + size(p->right));
 }
}
/*
Given a binary search tree, print out
its data elements in increasing
sorted order.
 */
void printTree(struct node* node) {
 if (node == NULL) {//printf("check");
  return;}
 printTree(node->left);
 printf("%d <<", node->data);
 printTree(node->right);
}
void printPostTree(node *node)
{
 if (node == NULL) return;
 printPostTree(node->left);//note here even printTree will work
 printPostTree(node->right);
 printf("%d ", node->data);
}
/*
The node to be deleted might be in the following states
 * The node does not exist in the tree - In this case you have nothing to delete.
 * The node to be deleted has no children - The memory occupied by this node must
be freed and either the left link or the right link of the parent of this node must be set to NULL.
 * The node to be deleted has exactly one child -
We have to adjust the pointer of the parent of the node to be deleted such that
after deletion it points to the child of the node being deleted.
 * The node to be deleted has two children -
We need to find the inorder successor of the node to be deleted.
The data of the inorder successor must be copied into the node to be deleted and a pointer should
be setup to the inorder successor. This inorder successor would have one or zero children.
This node should be deleted using the same procedure as for deleting a one child or a zero child node.
Thus the whole logic of deleting a node with two children is to locate the inorder successor,
copy its data and reduce the problem to a simple deletion of a node with one or zero children.*/
int select()
{
 int selection;
 do
 {
  puts("");
  puts("Enter 1: Insert a node in the BST");
  puts("Enter 2: Delete");
  puts("Enter 3: Display(preorder)the BST");
  puts("Enter 4: Display(inorder)the BST");
  puts("Enter 5: Display(postorder) the BST");
  puts("Enter 6: Print");
  puts("Enter 7: Lookup");
  puts("Enter 9: End");
  puts("Enter your choice");
  scanf("%d",&selection);
  if((selection<1)||(selection>7))
  {
   puts("wrong choice:Try again");
   getch(); }
 }while((selection<1)||(selection>7));
 return (selection);
}
node *getInorder2Child(node *n)//returns inorder succesor only when parent has //right node
{
 if( n->right==0 ) return 0;
 n = n->right;
 while( n->left != 0 )
  n = n->left;
  return n;
}
node *child0(node *p, node **parent,int rt,int lt)
{
 node *parentP = *parent;
 if(rt==1) parentP->right = NULL;
 else if(lt==1) parentP->left = NULL;
 //retNode = p;
 //free(p);//free only when u dont want to return the node and adjust return type accordingly
 return p;
}
node *child_1(node *p, node **parent, int rt,int lt)
{
 node *parentP = *parent;
 if(p->left==NULL && p->right!=NULL)
 {
  if(rt==1) parentP->right = p->right;
  else parentP->left = p->right;
 }
 if(p->left!=NULL&&p->right==NULL)
 {
  if(rt==1) parentP->right = p->left;
  else parentP->left = p->left;
 }
}
node * deleteNode(node **root,int num)
{
 int lt=0,rt=0,inorderData;
 node *p = *root,*parentP=*root;
 node *retNode;
 node *inordersucc;
 if(!lookup(*root,num)) {printf("node not found\n");
 return (node*) 0;
 }
 //if node to be deleted has no child
 while(p->data!=num)
 {
  if(p->data > num) { parentP=p; p=p->left; lt=1;rt=0;}
  else if(p->dataright; lt=0;rt=1;}
}
if(isChildless(p))
{
 p = child0(p,&parentP,rt,lt);
 return p;
}
//only 1 child to be deleted
if((p->left==NULL && p->right!=NULL)||(p->left!=NULL&&p->right==NULL))
{
 p=child_1(p,&parentP,rt,lt);
 return p;
}
if(p->left!= NULL && p->right != NULL)
{
 inordersucc = getInorder2Child(p);
 // printf("%d\n" , inordersucc->data);
 //swap teh values
 // swaptemp = num;//though swaptemp is useless variable, because we already have num
 p->data = inordersucc->data;
 //inordersucc->data = num;
 //printf("%d\n",inordersucc->data);
 retNode = deleteNode(&p->right,inordersucc->data);
}
return (node*) NULL;
}
#endif

Let us know the feedback.

Read More

Deleting a node from a Binary Search Tree

Suppose we want to delete a node k. First we need to search for the node k. Offcourse k should not be null.

Then we have three cases:

1. The node to be deleted has no children - The memory occupied by this node must be freed and either the left link or the right link of the parent of this node must be set to NULL.

2. The node to be deleted has exactly one child -
We have to adjust the pointer of the parent of the node to be deleted such that after deletion it points to the child of the node being deleted.

3. The node to be deleted has two children -
We need to find the inorder successor of the node to be deleted.
The data of the inorder successor must be copied into the node to be deleted and a pointer should be setup to the inorder successor. This inorder successor would have one or zero children.
This node should be deleted using the same procedure as for deleting a one child or a zero child node.
Thus the whole logic of deleting a node with two children is to locate the inorder successor, copy its data and reduce the problem to a simple deletion of a node with one or zero children.

Case 1: The node to be deleted has no children
Example. Remove 1 from a BST.

 Remove 1 , that's all.

Case 2: The node to be deleted has 1 child
Example. Remove 18 from a BST.

After removing the node, we just append 1 to 5.

Case 3: Node to be deleted has 2 children

This is the most complex case. Consider the tree below , suppose we want to delete the node 3 from the tree. Here we update the node such that we will reduce it to case 1 or 2. 

How do we calculate inorder successor or predecessor?

Here we have to find the inorder successor or predecessor L of node K - the node which has to be deleted. So here the next small element which is smaller than 3 is 2, i.e. L. 

We already know how to calculate predecessor L. What it depends on is whether the node to be deleted has non-empty left sub tree. If the tree has non-null left sub tree then just go to the right most child of the tree. So, here because we have 2 children, so this case will always prevail. 

Approaching the problem now

The same approach can be utilized to remove a node, which has two children:

• find a minimum value in the right subtree(this is the inorder successor of the node to be deleted).
• replace value of the node to be removed with found minimum. Now, right subtree contains a duplicate!
• apply remove to the right subtree to remove a duplicate, that is call remove function(in our case delete) with right subtree now as root node.
  

Apply this on the example:
Finding the inorder successor

Swap inorder successor with node to be deleted , here 3

Now, we have to delete 3, which fits in the case 1 - node with no child, just delete it :)

Here is the function I implemented:

A node can be removed from a Binary Search Tree using two approaches.
1. Double Pointer Approach
2. Single Pointer Approach

Double pointer approach:

void remove(BinaryTreeNode **node, int data)
{
   if(*node == NULL)
   {
     std::cerr << "ERROR: Node does not exist\n";
   }
 
   if(data == (*node)->data)
   {
     if((*node)->right == NULL)
     {
       *node = (*node)->left;
     }
     else if((*node)->left == NULL)
     {
       *node = (*node)->right;
     }
     else
     {
       BinaryTreeNode **successor = getSuccessor(&(*node)->left);
       (*node)->data = (*successor)->data;
       remove(successor, (*successor)->data);
     }
   }
   else if(data < (*node)->data)
   {
     remove(&(*node)->left, data);
   }
   else
   {
     remove(&(*node)->right, data);
   }
}
 
//Tricky
BinaryTreeNode** getSuccessor(BinaryTreeNode **node)
{
  BinaryTreeNode **tmp = node;
  while((*tmp)->right != NULL)
    tmp = &(*tmp)->right;
  return tmp;
}

Single pointer approach
Note the difference between single pointer and double pointer approach. The difference help in clarifying how pointers work in C/C++

BinaryTreeNode* remove(BinaryTreeNode *node, int data)
{
  if(node == NULL)
  {
    std::cerr << "ERROR: Node does not exists\n";
    return node;
  }
 
  if(data == node->data)
  {
    BinaryTreeNode *retval = NULL;
  
    if(node->left == NULL)
    {
      retval = node->right;
      delete node;
      return retval;
    }
    else if(node->right == NULL)
    {
      retval = node->left;
      delete node;
      return retval;
    }
    else
    {
       BinaryTreeNode *successor = getSuccessor(node->left);
       node->data = successor->data;
       node->left = remove(node->left, successor->data);
    }
  }
  else if(data < node->data)
  {
    node->left = remove(node->left, data);
  }
  else
  {
    node->right = remove(node->right, data);
  }
 
  return node;
}
 
BinaryTreeNode* getSuccessor(BinaryTreeNode *node)
{
  while(node->right != NULL)
    node = node->right;
  return node;
}

Implementing the same in java

private BinaryTreeNode remove(BinaryTreeNode node, int data)
{
  if(node == null)
  {
    System.out.println("ERROR: Number does not exist");
    return null;
  }
 
  if(data == node.data)
  {
    if(node.left == null)
    {
      return node.right;
    }
    else if(node.right == null)
    {
      return node.left;
    }
    else //both the children exists
    {
      BinaryTreeNode successor = getSuccessorNode(node.left);
      node.data = successor.data;
      node.left = remove(node.left, successor.data);
    }
  }
  else if(data < node.data)
  {
    node.left = remove(node.left, data);
  }
  else
  {
    node.right = remove(node.right, data);
  }
 
  return node;
}
 
private BinaryTreeNode getSuccessorNode(BinaryTreeNode node)
{
  while(node.right != null)
  {
    node = node.right;
  }
  return node;
}

Read More

Inorder successor OR Predecessor of BST node

It is important to understand inorder successor of BST because it helps us understand deletion of node from a tree, when the node deleted has 2 children.

To find the inorder successor of node u:

• If u has a right child, r, then succ(u) is the leftmost descendent of r

• Otherwise, succ(u) is the closest ancestor, v, of u (if any) such that u is descended from the left child of v. If there is no such ancestor, then succ(u) is undefined.
  

An iterator would start with the leftmost node.

For example, an inorder traversal of the following binary tree yields the sequence DBFGEAC.

Taking the nodes one at a time and applying the rule:
node D: Does not have a right child. Its successor is the closest ancestor, v
such that node-D is descended from the left child of v. Node-D is descended
from the left child of node-B, so succ(D) is node-B.

node B: Has a right child (node-E), so successor is the leftmost descendent of
node-E, namely node-F.

node F: Has a right child (node-G), so successor is the leftmost descendent of
node-G, namely node-G itself.

node G: Does not have a right child. Its successor is the closest ancestor, v
such that node-G is descended from the left child of v. Node-G is descended
from the left child of node-E, so succ(G) is node-E.

node E: Does not have a right child. Its successor is the closest ancestor, v
such that node-E is descended from the left child of v. Node-E is descended
from the left child of node-A, so succ(E) is node-A

node A: Has a right child (node-C), so successor is the leftmost descendent of
node-C, namely node-C itself.

node C: Does not have a right child. Its successor would be the closest ancestor,
v such that node-C is descended from the left child of v. However,
there is no such ancestor, so succ(C) is unde ned (node-C has no successor).

To summarize in table :

Node	Successor
A	C
B	F
C	NONE
D	B
E	A
F	G
G	E

Thanks

Read More

Implementing BST in C ( header file )

This post contains header file which contains binary search tree related function. The tree contains following functions:

• Search
• Create new node
• Get the size of tree
• Insert
• Delete
• Print inorder, pre order and post order

Starting the header file:

Lets name our header file as Tree1.h.

#ifndef TREE1_H
#define TREE1_H

#include <stdio.h>
#include <malloc.h>

enum BOOL{false,true};

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

typedef struct node node;
typedef enum BOOL BOOL;

 

Defining some functions via c macros:

#define isChildless(p) p->left==NULL &&p->right==NULL

Providing the Search function

/*
Given a binary tree, return true if a node
with the target data is found in the tree. Recurs
down the tree, chooses the left or right
branch by comparing the target to each node.
*/
static int lookup(node* node, int target) {
// 1. Base case == empty tree
// in that case, the target is not found so return false
    if (node == NULL) {
    return(false);
    }
    else {
// 2. see if found here
    if (target == node->data)
         return(true);
    else {
// 3. otherwise recur down the correct subtree
        if (target < node->data)
             return(lookup(node->left, target));
        else return(lookup(node->right, target));
    }
  }
}

Getting the new node:

/*gets the node of tree with value initialized with data*/
node* newNode(int data) {
node* temp = (node*) malloc(sizeof(node)); // "new" is like "malloc"
temp->data = data;
temp->left = NULL;
temp->right = NULL;

return(temp);
}

Insert new node in the tree (function)

/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree.
Returns the new root pointer which the caller should
then use (the standard trick to avoid using reference
parameters).
*/
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
   }
}

Get the size of BST tree function:

//functions simply on traversals
int size(node *p)
{
    if (p==NULL) {
        return(0);
    } else {
        return(size(p->left) + 1 + size(p->right));
    }
}

Traversing the BST tree function

/*
Given a binary search tree, print out
its data elements in increasing
sorted order.
*/
void printTree(struct node* node) {
    if (node == NULL) {//printf("check");
        return;
    }
    
    printTree(node->left);
    printf("%d <<", node->data);
    printTree(node->right);
}

void printPostTree(node *node)
{
    if (node == NULL) return;
    
    printPostTree(node->left);//note here even printTree will work
    printPostTree(node->right);
    printf("%d ", node->data);
    
}

Deleting the node from BST function:

Note that I have provided for logic of BST deletion of node here.

/*
The node to be deleted might be in the following states


* The node does not exist in the tree - In this case you have nothing to delete.
* The node to be deleted has no children - The memory occupied by this node must
be freed and either the left link or the right link of the parent of this node must be set to NULL.
* The node to be deleted has exactly one child -
We have to adjust the pointer of the parent of the node to be deleted such that
after deletion it points to the child of the node being deleted.
* The node to be deleted has two children -
We need to find the inorder successor of the node to be deleted.
The data of the inorder successor must be copied into the node to be deleted and a pointer should
be setup to the inorder successor. This inorder successor would have one or zero children.
This node should be deleted using the same procedure as for deleting a one child or a zero child node.
Thus the whole logic of deleting a node with two children is to locate the inorder successor,
copy its data and reduce the problem to a simple deletion of a node with one or zero children.*/
node * deleteNode(node **root,int num)
{
    int lt=0,rt=0,inorderData;
    node *p = *root,*parentP=*root;
    node *retNode;
    node *inordersucc;
    if(!lookup(*root,num)) {
        printf("node not found\n");
        return (node*) 0;
    }
    //if node to be deleted has no child
    while(p->data!=num)
    {
        if(p->data > num) {
             parentP=p; p=p->left; lt=1;rt=0;}
        else if(p->data>num) {
             parentP = p; p=p->right; lt=0;rt=1;
        }
    }
    
    if(isChildless(p))
    {
        p = child0(p,&parentP,rt,lt);
        return p;
    }
    
    //only 1 child to be deleted
    if((p->left==NULL && p->right!=NULL)||(p->left!=NULL&&p->right==NULL))
    {
        p=child_1(p,&parentP,rt,lt);
        return p;
    }
    
    if(p->left!= NULL && p->right != NULL)
    {
        inordersucc = getInorder2Child(p);
    // printf("%d\n" , inordersucc->data);
    //swap teh values
    // swaptemp = num;//though swaptemp is useless variable, because we already have num
    
        p->data = inordersucc->data;
    //inordersucc->data = num;
    //printf("%d\n",inordersucc->data);
        retNode = deleteNode(&p->right,inordersucc->data);
        return retNode;
    }
    return (node*) NULL;
}

Clearly we require 2 functions -  child_0 and child_1 as well

/*returns inorder succesor only when parent has //right node*/
node *getInorder2Child(node *n)
{

    if( n->right==0 )
         return 0;
    n = n->right;
    
    while( n->left != 0 )
        n = n->left;
    
    return n;
}

node *child0(node *p, node **parent,int rt,int lt)
{
    node *parentP = *parent;
    
    if(rt==1) 
        parentP->right = NULL;
    else if(lt==1) 
        parentP->left = NULL;
    //retNode = p;
    //free(p);//free only when u dont want to return the node and adjust return type accordingly
    return p;
    
}

node *child_1(node *p, node **parent, int rt,int lt)
{
    node *parentP = *parent;
    if(p->left==NULL && p->right!=NULL)
    {
        if(rt==1)
             parentP->right = p->right;
        else
             parentP->left = p->right;
    }
    if(p->left!=NULL&&p->right==NULL)
    {
        if(rt==1)
             parentP->right = p->left;
        else 
             parentP->left = p->left;
    }
}

Close the header file

#endif

That's it. Our header file is prepared, but what about delete. So here is another article which covers delete function as well.

Read More