Explore topic-wise InterviewSolutions in Current Affairs.

• An ABSTRACT data type is the specification of the data type which SPECIFIES the LOGICAL and mathematical MODEL of the data type.
• A data type is the implementation of an abstract data type.
• Data structure refers to the collection of COMPUTER variables that are connected in some specific manner.

i.e) Data type has its root in the abstract data type and a data structure comprises a set of computer variables of same or different data types.

i.e) Data type has its root in the abstract data type and a data structure comprises a set of computer variables of same or different data types.

Data type refers to the kinds of data that VARIABLES may hold in the programming language. Eg) int, float, char, double – C

The following are the TYPES of data type:

• BUILT in data type- int, float, char, double which are defined by programming language itself
• User defined data type- Using the set of built in data types user can define their own data type

Eg: typedef struct STUDENT

Where S is a tag for user defined data type which defines the STRUCTURE student and s1 is a variable of data type S.

Data type refers to the kinds of data that variables may hold in the programming language. Eg) int, float, char, double – C

The following are the types of data type:

Eg: typedef struct student

Where S is a tag for user defined data type which defines the structure student and s1 is a variable of data type S.

An abstract DATA type is a set of operations. ADTs are MATHEMATICAL abstractions; now here in an ADT’s definition is there any mention of how the set of operations is implemented. Objects such as lists, SETS and graphs, along with their operations can be VIEWED as abstract data types.

An abstract data type is a set of operations. ADTs are mathematical abstractions; now here in an ADT’s definition is there any mention of how the set of operations is implemented. Objects such as lists, sets and graphs, along with their operations can be viewed as abstract data types.

• It is much EASIER to debug small ROUTINES than large routines
• It is easier for several PEOPLE to WORK on a modular PROGRAM simultaneously
• A well-written modular program places certain dependencies in only one routine, making changes easier

Primitive DATA types are the fundamental data types. Eg) INT, float, double, CHAR Non-primitive data types are USER defined data types. Eg) STRUCTURE, Union and enumerated data types.

Primitive data types are the fundamental data types. Eg) int, float, double, char Non-primitive data types are user defined data types. Eg) Structure, Union and enumerated data types.

Persistent DATA structures are the data structures which RETAIN their PREVIOUS state and modifications can be DONE by performing certain operations on it. Eg) Stack Ephemeral data structures are the data structures which cannot retain its previous state. Eg) Queues.

Persistent data structures are the data structures which retain their previous state and modifications can be done by performing certain operations on it. Eg) Stack Ephemeral data structures are the data structures which cannot retain its previous state. Eg) Queues.

• To IDENTIFY and create USEFUL mathematical ENTITIES and OPERATIONS to determine what classes of PROBLEMS can be solved using these entities and operations.
• To determine the representation of these abstract entities and to implement the abstract operations on these concrete representation.

• Linear Queues – The queue has two ends, the front END and the rear end. The rear end is where we insert elements and front end is where we DELETE elements. We can traverse in a linear queue in only one DIRECTION ie) from front to rear.
• Circular Queues – Another form of linear queue in which the last position is CONNECTED to the first position of the list. The circular queue is similar to linear queue has two ends, the front end and the rear end. The rear end is where we insert elements and front end is where we delete elements. We can traverse in a circular queue in only one direction ie) from front to rear.
• Double-Ended-Queue – Another form of queue in which insertions and DELETIONS are made at both the front and rear ends of the queue.

• Towers of Hanoi
• REVERSING a string
• Balanced parenthesis
• RECURSION USING stack
• EVALUATION of ARITHMETIC expressions

• Jobs submitted to PRINTER
• REAL life line
• Calls to LARGE COMPANIES
• Access to limited resources in Universities
• Accessing files from file SERVER

MANY languages such as BASIC and FORTRAN do not support pointers. If linked LISTS are required and pointers are not available, then an alternative implementation must be used KNOWN as cursor implementation.

Many languages such as BASIC and FORTRAN do not support pointers. If linked lists are required and pointers are not available, then an alternative implementation must be used known as cursor implementation.

A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of a distinguished node r, called the root, and zero or more nonempty (sub) trees T1, T2,…,Tk, each of whose roots are CONNECTED by a DIRECTED edge from r.

A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of a distinguished node r, called the root, and zero or more nonempty (sub) trees T1, T2,…,Tk, each of whose roots are connected by a directed edge from r.

This is the UNIQUE NODE in the TREE to which further sub-trees are ATTACHED.

This is the unique node in the tree to which further sub-trees are attached.

The TOTAL NUMBER of sub-trees attached to that NODE is called the degree of the node.

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

These are the TERMINAL nodes of the TREE. The nodes with degree 0 are always the LEAVES.

Here C and B are the LEAVE nodes.

These are the terminal nodes of the tree. The nodes with degree 0 are always the leaves.

Here C and B are the leave nodes.

The NODES other than the ROOT and the LEAVES are CALLED INTERNAL nodes.

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

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.

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.

For any NODE ni, the depth of ni is the length of the UNIQUE path from the ROOT to ni. The height of ni is the length of the longest path from ni to a LEAF.

For any node ni, the depth of ni is the length of the unique path from the root to ni. The height of ni is the length of the longest path from ni to a leaf.

The depth of the TREE is the depth of the DEEPEST LEAF. The height of the tree is EQUAL to the height of the root. Always depth of the tree is equal to height of the tree.

The depth of the tree is the depth of the deepest leaf. The height of the tree is equal to the height of the root. Always depth of the tree is equal to height of the 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.

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.

A TREE may be DEFINED as a forest in which only a SINGLE NODE (root) has no PREDECESSORS. Any forest consists of a collection of trees.

A tree may be defined as a forest in which only a single node (root) has no predecessors. Any forest consists of a collection of trees.

A BINARY tree is a finite set of NODES which is either EMPTY or consists of a root and two disjoint binary trees called the LEFT sub-tree and right sub-tree.

A binary tree is a finite set of nodes which is either empty or consists of a root and two disjoint binary trees called the left sub-tree and right sub-tree.

A PATH in a TREE is a sequence of distinct nodes in which SUCCESSIVE nodes are CONNECTED by EDGES in the tree.

A path in a tree is a sequence of distinct nodes in which successive nodes are connected by edges in the tree.

A node that has no CHILDREN is called a TERMINAL node. It is also REFERRED to as LEAF node.

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

All INTERMEDIATE nodes that traverse the GIVEN tree from its root node to the TERMINAL nodes are REFERRED as non-terminal nodes.

All intermediate nodes that traverse the given tree from its root node to the terminal nodes are referred as non-terminal nodes.

A full binary tree is a tree in which all the LEAVES are on the same LEVEL and EVERY non-leaf node has exactly TWO CHILDREN.

A full binary tree is a tree in which all the leaves are on the same level and every non-leaf node has exactly two children.

A COMPLETE BINARY tree is a tree in which every non-leaf NODE has EXACTLY two CHILDREN not necessarily to be on the same level.

A complete binary tree is a tree in which every non-leaf node has exactly two children not necessarily to be on the same level.

A RIGHT-skewed BINARY TREE is a tree, which has only right CHILD NODES.

A right-skewed binary tree is a tree, which has only right child nodes.

• The maximum number of nodes on level N of a binary TREE is 2n-1, where n≥1.
• The maximum number of nodes in a binary tree of HEIGHT n is 2n-1, where n≥1.
• For any non-empty tree, NL=nd+1 where nl is the number of leaf nodes and nd is the number of nodes of degree 2.

Traversing a binary TREE MEANS moving through all the nodes in the binary tree, VISITING each node in the tree only once.

Traversing a binary tree means moving through all the nodes in the binary tree, visiting each node in the tree only once.

• PREORDER TRAVERSAL.
• INORDER traversal.
• POSTORDER traversal.
• Levelorder traversal.

• VISITING a NODE.
• TRAVERSE the LEFT sub-tree.
• Traverse the RIGHT sub-tree.

• PROCESS the ROOT node.
• TRAVERSE the left sub-tree.
• Traverse the right sub-tree.

• TRAVERSE the left sub-tree.
• PROCESS the ROOT NODE.
• Traverse the right sub-tree.

• TRAVERSE the left sub-tree.
• Traverse the right sub-tree.
• Process the ROOT NODE.

• Storage method is easy and can be EASILY implemented in arrays.
• When the location of a parent/child node is known, other one can be DETERMINED easily.
• It requires STATIC memory allocation so it is easily implemented in all PROGRAMMING language.

INSERTIONS and deletions in a NODE take an EXCESSIVE amount of processing TIME due to data movement up and down the array.

Insertions and deletions in a node take an excessive amount of processing time due to data movement up and down the array.

Insertions and deletions in a NODE involve no data movement except the rearrangement of POINTERS, hence LESS processing TIME.

Insertions and deletions in a node involve no data movement except the rearrangement of pointers, hence less processing time.

• 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.

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.

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

GENERAL TREE is a tree with NODES having any NUMBER of CHILDREN.

General tree is a tree with nodes having any number of children.

If there is a PATH from NODE n1 to N2, then n1 is the ANCESTOR of n2 and n2 is the DESCENDANT of n1.

If there is a path from node n1 to n2, then n1 is the ancestor of n2 and n2 is the descendant of n1.

In binary search tree, the nodes are arranged in such a way that the left node is having less data value than ROOT node value and the right nodes are having larger value than that of root. Because of this while searching any node the value of the TARGET node will be compared with the parent node and accordingly either left sub branch or right sub branch will be searched. So, ONE has to compare only PARTICULAR branches. Thus searching BECOMES efficient.

In binary search tree, the nodes are arranged in such a way that the left node is having less data value than root node value and the right nodes are having larger value than that of root. Because of this while searching any node the value of the target node will be compared with the parent node and accordingly either left sub branch or right sub branch will be searched. So, one has to compare only particular branches. Thus searching becomes efficient.

In THREADED BINARY tree, the NULL POINTERS are replaced by some addresses. The left pointer of the NODE points to its predecessor and the right pointer of the node points to its successor.

In threaded binary tree, the NULL pointers are replaced by some addresses. The left pointer of the node points to its predecessor and the right pointer of the node points to its successor.

An EXPRESSION tree is a tree which is build from infix or PREFIX or postfix expression. GENERALLY, in such a tree, the leaves are OPERANDS and other nodes are operators.

An expression tree is a tree which is build from infix or prefix or postfix expression. Generally, in such a tree, the leaves are operands and other nodes are operators.

Right-in THREADED binary tree is defined as one in which THREADS REPLACE NULL pointers in nodes with empty right sub-trees.

Right-in threaded binary tree is defined as one in which threads replace NULL pointers in nodes with empty right sub-trees.

Left-in threaded binary TREE is DEFINED as ONE in which each NULL pointers is altered to CONTAIN a thread to that node’s inorder PREDECESSOR.

Left-in threaded binary tree is defined as one in which each NULL pointers is altered to contain a thread to that node’s inorder predecessor.

An empty tree is height balanced. If T is a non-empty BINARY tree with TL and TR as its LEFT and right subtrees, then T is height balanced if

1. TL and TR are height balanced and
2. │HL - hR│≤ 1

Where hL and hR are the heights of TL and TR respectively.

An empty tree is height balanced. If T is a non-empty binary tree with TL and TR as its left and right subtrees, then T is height balanced if

Where hL and hR are the heights of TL and TR respectively.

BALANCED TREES have the structure of binary trees and obey binary search tree properties. Apart from these properties, they have some special constraints, which differ from one data structure to another. However, these constraints are aimed only at reducing the height of the tree, because this factor determines the time complexity.

EG: AVL trees, SPLAY trees.

Balanced trees have the structure of binary trees and obey binary search tree properties. Apart from these properties, they have some special constraints, which differ from one data structure to another. However, these constraints are aimed only at reducing the height of the tree, because this factor determines the time complexity.

Eg: AVL trees, Splay trees.

Let A be the nearest ANCESTOR of the newly INSERTED NOD which has the balancing factor ±2. 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.

Let A be the nearest ancestor of the newly inserted nod which has the balancing factor ±2. 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.