Nonrecursive/Iterative Binary Search Tree in C (Homework)

How can I create/delete a node in a Binar开发者_JAVA技巧y Search Tree using Iterative Algorithm in C?

---

Iterative insertion:

struct tree_node *Insert_Element (struct tree_node *root, void *key, void *data) {
  struct tree_node *new_node, *node;

  node = root;

  do {    
    switch (compare(key, node->key)) {

      case -1: {
        if (node->left == NULL) {
          if ((new_node = create_node(key, data)) == NULL) {
            return NULL;
          }

          node->left = new_node;    
          return new_node;
        }

        node = node->left;
      } break;

      case 1: {
        if (node->right == NULL) {
          if ((new_node = create_node(key, data)) == NULL) {
            return NULL;
          }

          node->right = new_node;
          return new_node;
        }

        node = node->right;
      } break;

      default: {    
        return node;
      }
    }
  } while (node != NULL);

  return NULL;
}

---

Iterative insertion & deletion in BST

struct bst {
    int data;
    struct bst *left;
    struct bst *right;
};
typedef struct bst bst_t;

bst_t *get_new_node(int val)
{
    bst_t *node = (bst_t *) malloc(sizeof(bst_t));
    node->data = val;
    node->left = NULL;
    node->right= NULL;
    return node;
}  

bst_t *insert(bst_t *root, int val)
{   
    if(!root) return get_new_node(val);
    bst_t *prev = NULL, *ptr = root;
    char type = ' ';
    while(ptr) {
        prev = ptr;
        if(val < ptr->data) {
            ptr = ptr->left;
            type = 'l';
        } else {
            ptr = ptr->right;
            type = 'r';
        }
    }
    if(type == 'l') 
        prev->left  = get_new_node(val);
    else 
        prev->right = get_new_node(val);
    return root;
}  

int find_minimum_value(bst_t *ptr)
{
    int min = ptr ? ptr->data : 0;
    while(ptr) {                        
        if(ptr->data < min) min = ptr->data;
        if(ptr->left) {         
            ptr = ptr->left;            
        } else if(ptr->right) {
            ptr = ptr->right;
        } else ptr = NULL;
    }
    return min;
}  

bst_t *delete(bst_t *root, int val) 
{
    bst_t *prev = NULL, *ptr = root;
    char type = ' ';    
    while(ptr) {
        if(ptr->data == val) {          
            if(!ptr->left && !ptr->right) { // node to be removed has no children's
                if(ptr != root && prev) { // delete leaf node
                    if(type == 'l') 
                        prev->left = NULL;
                    else
                        prev->right = NULL;
                } else root = NULL; // deleted node is root
            } else if (ptr->left && ptr->right) { // node to be removed has two children's              
                ptr->data = find_minimum_value(ptr->right); // find minimum value from right subtree                    
                val = ptr->data;
                prev = ptr;
                ptr = ptr->right; // continue from right subtree delete min node 
                type = 'r';
                continue;               
            } else { // node to be removed has one children             
                if(ptr == root)  { // root with one child                   
                    root = root->left ? root->left : root->right;   
                } else { // subtree with one child
                    if(type == 'l') 
                        prev->left = ptr->left ? ptr->left : ptr->right;
                    else
                        prev->right = ptr->left ? ptr->left : ptr->right;   
                }           
            }
            free(ptr);
        }
        prev = ptr; 
        if(val < ptr->data) {           
            ptr = ptr->left;
            type = 'l';
        } else {
            ptr = ptr->right;
            type = 'r';
        }
    } 
    return root;
}

---

Nice post. Just a suggestion. I believe, finding a minimum value in a BST doesn't have to traverse the right subtree. Minimum value must be either on the left subtree or node itself(in case if left subtree is null). Function find_minimum_value can be optimized if right subtree traversal is removed.

int find_minimum_value(bst_t *ptr)
{
    while(ptr->left) {                               
        ptr = ptr->left;
    }
    return ptr->data;
} 

---

In C, you can cast the pointers in the tree to intptr_t type and perform bitwise operations to them.

As you traverse down the tree, you can store the 'parent' pointer of a node by xoring it with the pointer you traversed with. You can then traverse back up the tree by xoring the the address of the node you are coming from with the modified pointer.

A worked example of this traditional technique is at http://sites.google.com/site/debforit/efficient-binary-tree-traversal-with-two-pointers

Given the ability to traverse the tree without recursion, you can then create iterative versions of any of the algorithms based on traversing the tree.