img
Question:
Published on: 1 July, 2022

a) Write an algorithm for deletion of a node from a doubly-linked list. 

b) What is a threaded binary tree ? Write an algorithm for non-recursive in-order traversal of a threaded binary tree. 

Answer:

a) Algorithm:
Let the node to be deleted is del.
1) If node to be deleted is head node, then change the head pointer to next current head.
2) Set next of previous to del, if previous to del exixts.
3) Set prev of next to del, if next to del exixts.

struct node {

  int data;

  struct node *next;

  struct node *prev;

};

void deleteNode(struct node **head_ref, struct node *del) {

  /* base case */

  if(*head_ref == NULL || del == NULL)

    return;

  /* If node to be deleted is head node */

  if(*head_ref == del)

       *head_ref = del->next;

 

  /* Change next only if node to be deleted is NOT the last node */

  if(del->next != NULL)

    del->next->prev = del->prev;

 

  /* Change prev only if node to be deleted is NOT the first node */

  if(del->prev != NULL)

    del->prev->next = del->next;    

   /* Finally, free the memory occupied by del*/

  free(del);

  return;

}

 

b) A threaded binary tree is a binary tree variant that allows fast traversal: given a pointer to a node in a threaded tree, it is possible to cheaply find it in-order successor (and/or predecessor).

Threads are constructed using the following rules:

– A 0 rightChild field at node p is replaced by a pointer to the node that would be visited afterp when traversing the tree in inorder. Thatis, It is replaced by the inorder successor of p.

– A 0 leftChild link at node p is replaced by a pointer to the node that immediately precedes node p in inorder (i.e., it is replaced by the inorder predecessor of p).

 

 

 

 

 

 

 

 

 

 

 

"

Random questions