virtualgate's picture

Linked List , Trees

Introduction to Linked List
Content covered: 

Introduction to linked list, Structure of a node of linked list

More Less
0Comment
Linked list operations
Content covered: 

Linked list operations:
1. Insert a node at the start of the linked list
2. Search a node value 
3. Insert a new node after a node in linked list
4. Delete a node after a given node in linked list
5. Insert before a node
6. Traversing a linked list

More Less
0Comment
Introduction to binary tree
Content covered: 

Introduction to binary tree

More Less
0Comment
Different Binary tree possible | Labelled and unlabelled
Content covered: 

Different Binary tree possible for Labelled and unlabelled nodes

More Less
0Comment
Questions on traversal of binary trees
Content covered: 

Questions on traversal of binary trees

More Less
0Comment
Introduction to AVL Trees
Content covered: 

Introduction to AVL Trees: Various rotations to create AVL tree.

More Less
0Comment
Trees: Important Formulas and Recursive Equations

Important formulas:
Number of unlabelled binary trees possible with n nodes = 2nCn/(n+1)
Number of labelled binary trees possible with n nodes = (2nCn/(n+1)) x n!
With n nodes and a given preorder, total number of  binary trees possible = 2nCn/(n+1)
With a given inorder and any one of preorder or postorder, total numbar of binary trees possible = 1
For a complete n-ary tree having X internal nodes, the total number of leaves  = X(n-1)+1
For a binary tree having n leaf nodes, total number of nodes of degree two = n-1
The maximum number of nodes in a binary tree of height 'h' = 2h+1-1
The minimum number of nodes in a binary tree of height h = h+1

Important Recursive Equations:
T- Pointer to the root of the tree 
NN- Number of nodes
LST- Pointer to Left Sub Tree
RST- Pointer to Right Sub Tree

1.Counting number of nodes 

NN(T)    = 0; if T is Null
              =  1+NN(LST)+NN(RST);otherwise

2.Counting number of leaves

NN(T)    = 1; if T is leaf
              =  NN(LST)+NN(RST);otherwise

3.Height H of a binary tree

H(T)    = 0; if T is Null or T is leaf
           =  1+max(H(LST),H(RST));otherwise

4.Counting number of full nodes (FN) in a binary tree

FN(T)  = 0; if T is Null or T is a leaf
           = FN(LST)+FN(RST); if T has only one child
           = 1+FN(LST)+FN(RST); if T is a full node

5.Counting minimum number of nodes in an AVL tree of height h

N(h)    = 1; if h=0
           = 2; if h=1
           = N(h-1)+1+N(h-2); otherwise

Time Complexities :

Operation BST Balanced BST
Search O(n) O(log n)
Finding Height O(n) O(log n)
Insertion O(n) O(log n)
Deletion O(n) O(log n)

 

Contributor's Info

Created: Edited:
0Comment
GATE 2010 Question on Linked List
Content covered: 

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node

{

  int value;

  struct node *next;

}Node;

  

Node *move_to_front(Node *head)

{

  Node *p, *q;

  if ((head == NULL: || (head->next == NULL))

    return head;

  q = NULL; p = head;

  while (p-> next !=NULL)

  {

    q = p;

    p = p->next;

  }

  _______________________________

  return head;

}

Choose the correct alternative to replace the blank line.
(A) q = NULL; p->next = head; head = p;
(B) q->next = NULL; head = p; p->next = head;
(C) head = p; p->next = q; q->next = NULL;
(D) q->next = NULL; p->next = head; head = p;

More Less
0Comment

  • This quiz contains 10 questions on the topic Topic Name
  • Lean well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  intermediate