Function to count the number of terminal(leaf) nodes in a binary tree.

The function "terminal_count()" counts the number of leaf nodes of a binary tree.

int terminal_count(struct node *t)
{
  static int count = 0;
  if((t -> Llink == NULL) && (t -> Rlink == NULL))
    return 1;
  else
    count = count + terminal_count(t -> Llink) + terminal_count(t -> Rlink);
  return count;
}

Written by Munia Balayil

Height of a Binary Tree

Function to find the height of a binary tree

int height(struct node *t)
{
  if(t == NULL)
    return 0;
  int left = height(t -> Llink);
  int right = height(t -> Rlink);
  if(left > right)
    return left + 1;
  else 
    return right + 1; 
  }
}

Written by Munia Balayil

Reverse a Circular Doubly Linked List - Recursive Solution

Function to reverse a Circular Doubly Linked List

A doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.

The structure of a node in a Doubly linked list is as given below.

struct node
{
  struct node *Llink;
  int data;
  struct node *Rlink;
}

If we create the Doubly linked list in a circular fashion, it forms a Circular doubly linked list.

The function "reverse" reverses a circular doubly linked list with the head node given.

void swap(struct node *p,struct node *q)
{
  struct node *r;
  r = p;
  p = q;
  q = r;
}

void reverse(struct node *head)
{
  struct node *t = head -> Rlink;
  while(t != head)
  {
    swap(t -> Llink, t ->Rlink);
    t = t -> Llink;
  }
  swap(head -> Llink, head -> Rlink)
}

Written by Munia Balayil

Reverse a Linked List - Recursive Solution

Function to reverse a linked list - recursive solution

void reverse(struct node *pred, struct node *curr)
{
  if(curr)
  {
    reverse(curr, curr -> link);
    curr -> link = pred;
  }
  else
    first = pred;
}

void main()
{
  reverse(NULL, first);
}

Written by Munia Balayil

Reverse a Linked List - Iterative Solution

Function to reverse a linked list - iterative solution

void reverse(struct node *first)
{
  // p is used to traverse the linked list
  struct node *p = first;
  // q points to the start of the reversed list
  struct node *q = NULL;
  // r is a temporary variable used in this process
  struct node *r;

  while(p)
  {
    r = q;
    q = p;
    p = p -> link;
    q -> link = r;
  }
  first = q;
}

Written by Munia Balayil

Count the Number of Nodes in a Linked List - Recursive Solution

Function to count the number of nodes in a linked list - recursive solution

int count(struct node *p)
// p is a pointer to the first node of the list.
{
  if(p)
    return 1 + count(p->link);
  else
    return 0;
}

Written by Munia Balayil

Function to count the number of nodes in a linked list - iterative solution

int count(struct node *first)
// first is a pointer to the first node
{
  struct node *p = first;
  int count = 0;
  while(p)
  {
    ++count;
    p = p->link;
  }
  // Final value of count gives the number of nodes
  // in the linked list.
  return count;
}

Written by Munia Balayil