Question-31. How depth first traversal works?
Answer- Depth First Search algorithm(DFS) traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.
Question-32. How breadth first traversal works?
Answer- Breadth First Search algorithm(BFS) traverses a graph in a breadthwards motion and uses a queue to remember to get the next vertex to start a search when a dead end occurs in any iteration.
Question-33. What is a tree?
Answer- A tree is a minimally connected graph having no loops and circuits.
Question-34. What is a binary tree?
Answer- A binary tree has a special condition that each node can have two children at maximum.
Question-35. What is a binary search tree?
Answer- A binary search tree is a binary tree with a special provision where a node’s left child must have value less than its parent’s value and node’s right child must have value greater than it’s parent value.
Question-36. What is tree traversal?
Answer- Tree traversal is a process to visit all the nodes of a tree. Because, all nodes are connected via edges (links) we always start from the root (head) node. There are three ways which we use to traverse a tree−
• In-order Traversal • Pre-order Traversal • Post-order Traversal
Question-37.See the below image of a binary search tree, and traverse it using all available methods−
Answer-
• In-order traversal − 10 14 19 27 31 35 42 • Pre-order traversal − 27 14 10 19 35 31 42 • Post-order traversal − 10 19 14 31 42 35 27
Question-38. What is an AVL Tree?
Answer- AVL trees are height balancing binary search tree. AVL tree checks the height of left and right sub-trees and assures that the difference is not more than 1. This difference is called Balance Factor.
BalanceFactor = height(left-sutree) − height(right-sutree)
Question-39. What is a spanning tree?
Answer- A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. A spanning tree does not have cycles and it can not be disconnected.
Question-40. How many spanning trees can a graph has?
Answer- It depends on how connected the graph is. A complete undirected graph can have maximum nn-1 number of spanning trees, where n is number of nodes.