Data structure Quick reference - 10

56. How to check if a given binary tree is bst or not?
A binary search tree (BST) is a node based binary tree data structure which has the following properties.
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

57. What is Primary data structure?
Primary data structure, or a primitive data structure is one that is created from scratch, so to speak, without using other data structures as support or tool. This is the most basic and simple data structure, which is designed to operate upon by machine-level instructions.

58. What are static data structures?
A static data structure is an organization or collection of data in memory that is fixed in size. This results in the maximum size needing to be known in advance, as memory cannot be reallocated at a later point. Arrays are a prominent example of a static data structure.

59. What is a dynamic data structure?
A dynamic data structure (DDS) refers to an organization or collection of data in memory that has the flexibility to grow or shrink in size, enabling a programmer to control exactly how much memory is utilized.

60. What is the difference between BFS and DFS ?
The major difference between BFS and DFS is that BFS proceeds level by level while DFS follows first a path form the starting to the ending node (vertex), then another path from the start to end, and so on until all nodes are visited. Furthermore, BFS uses the queue for storing the nodes whereas DFS uses the stack for traversal of the nodes.

61. What is graph traversal ?
In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal.

62. What is minimum spanning tree ?
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

63. What is an acyclic graph?
An acyclic graph is a graph having no graph cycles. Acyclic graphs are bipartite. A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).

64. What is Degree, In Degree and Out degree ?
Degree: The degree of vertex is number of edges that are connected to the vertex. In above un directed graph, degree of vertex-1 is 2 and vertex 3 is 3.
In Degree: This is applicable only for directed graph. This represents the number of edges incoming to a vertex. In above directed graph, degree of 1 is 0 and degree of 2 is 2.
Out degree: This is also applicable only for directed graph. This represents the number of edges outgoing from a vertex. In above directed graph, degree of 1 is 2 and degree of 2 is 0.
1 2 3 4 5 6 7 8 9 10