Some of the static data structures in C are arrays, pointers, structures etc.

- Jobs submitted to printer
- Real life line
- Calls to large companies
- Access to limited resources in Universities
- Accessing files from file server

ii) Function’s data area is freed.

iii) Branch is taken to the return address.

VOID is a type identifier which has not size.

NULL and void are not same. Example: void* ptr = NULL;

The symbol “*” tells the computer that you are declaring a pointer. Actually it depends on context.

In a statement like int *ptr; the ‘*’ tells that you are declaring a pointer.

In a statement like int i = *ptr; it tells that you want to assign value pointed to by ptr to variable i.

The symbol “*” is also called as Indirection Operator/ Dereferencing Operator.

A binary search tree is a special binary tree, which is either empty or it should satisfy the following characteristics:

- Every node has a value and no two nodes should have the same value i.e) the values in the binary search tree are distinct.
- The values in any left sub-tree is less than the value of its parent node.
- The values in any right sub-tree is greater than the value of its parent node.
- The left and right sub-trees of each node are again binary search trees.

**Prefix Notation:**

^ – * +ABC – DE + FG

**postfix Notation:**

AB + C * DE – – FG + ^

Linear data structures are data structures having a linear relationship between its adjacent elements.

Eg; Linked lists.

- According to Access strategies Linked list is a linear one.
- According to Storage Linked List is a Non-linear one.

Definitions of member functions for the Linked List class are contained in the LinkedList.cpp file.

It is a collection of data elements called nodes, where each node is divided into three parts

i) An info field that contains the information stored in the node.

ii) Left field that contain pointer to node on left side.

iii) Right field that contain pointer to node on right side.

- Visiting a node.
- Traverse the left sub-tree.
- Traverse the right sub-tree.

The root node is always considered at level zero, then its adjacent children are supposed to be at level 1 and so on.

Here, node A is at level 0, nodes B and C are at level 1 and nodes D and E are at level 2.

Let A be the nearest ancestor of the newly inserted nod which has the balancing factor ±@Then the rotations can be classified into the following four categories:

**Left-Left:** The newly inserted node is in the left subtree of the left child of A.

**Right-Right:** The newly inserted node is in the right subtree of the right child of A.

**Left-Right:** The newly inserted node is in the right subtree of the left child of A.

**Right-Left:** The newly inserted node is in the left subtree of the right child of A.

- Given a node structure, it is difficult to determine its parent node.
- Memory spaces are wasted for storing null pointers for the nodes, which have one or no sub-trees.
- It requires dynamic memory allocation, which is not possible in some programming language.

The node which is having further sub-branches is called the parent node of those sub-branches.

Here C is the parent node of D and E.

Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.

Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.

- It is the mathematical way of representing the expression.
- It is easier to see visually which operation is done from first to last.

- Structure Property.
- Heap Order Property.

The nodes other than the root and the leaves are called internal nodes.

The total number of sub-trees attached to that node is called the degree of the node.

BFS performs simultaneous explorations starting from a common point and spreading out independently.

- It is not necessary to specify the number of elements in a linked list during its declaration.
- Linked list can grow and shrink in size depending upon the insertion and deletion that occurs in the list.
- Insertions and deletions at any place in a list can be handled easily and efficiently.
- A linked list does not waste any memory space.

The disadvantages of array are:

i) unlike linked list it is expensive to insert and delete elements in the array.

ii) One can’t double or triple the size of array as it occupies block of memory space.

In linked list

i) each element in list contains a field, called a link or pointer which contains the address of the next element.

ii) Successive element’s need not occupy adjacent space in memory.

- It is not necessary to specify the number of elements to be stored in a stack during its declaration, since memory is allocated dynamically at run time when an element is added to the stack.
- Insertions and deletions can be handled easily and efficiently.
- Linked list representation of stacks can grow and shrink in size without wasting memory space, depending upon the insertion and deletion that occurs in the list.
- Multiple stacks can be represented efficiently using a chain for each stack.

A node that has no children is called a terminal node. It is also referred to as leaf node.