Introduction
The term "tree traversal" refers to the process of visiting each node in a tree. There is only one method to traverse a linear data structure like a stack, queue, or linked list. However, there are several ways to travel or visit each node in a tree. The three alternative modes of tree traversal are as follows:
- Inorder tree traversal
- Preorder tree traversal
- Postorder tree traversal
Let us understand each traversal briefly:
-
Inorder tree traversal: A traversal approach that follows the policy, i.e., 'Left Root Right,' is an inorder tree traversal. 'Left Root Right' denotes that the root node's left subtree is read first, followed by the root node, and finally, the right subtree of the root node. The name 'in-order' implies that the root node is located between the left and right subtrees.
-
Preorder tree traversal: A preorder tree traversal is a traversal approach that follows the 'Root Left Right' policy. 'Root Left Right' indicates that the tree's root node is read first, followed by the left and right subtree. The name Pre-order demonstrates that the root node would be visited first in this case.
-
Postorder tree traversal: A traversal strategy that follows the policy, i.e., 'Left Right Root,' is known as a postorder tree traversal. 'Left Right Root' indicates that the root node's left subtree is read first, followed by the right subtree and the root node. The term "Postorder" implies that the tree's root node will be examined last.
Refer to Inorder, Preorder, Postorder, and Level Order tree traversals for better understanding and getting started with traversals and their approach.
Let us go through some of the crucial gate questions on tree traversal.
Gate Questions on Tree Traversal
Below are some commonly asked gate questions on tree traversal in the GATE examination.
1. Consider the rooted tree below, with P as the root vertex.
During in-order traversal, the nodes are visited in the following order:
a) SQPTRUWV
b) SQPTRWUV
c) SQPTURWV
d) SQPTWUVR
Ans. b) SQPTRWUV
Explanation:
In-order traversal algorithm (Left-Root-Right)
1) Call In-order to traverse the left subtree (left-subtree).
2) Head on down to the root.
3) Call In-order to traverse the right subtree (right-subtree).
Because the tree is not binary, the recursion is Left-Root-Middle-Right.
Go through our detailed description of the Inorder Traversal of a tree for detailed traversal.
2. Consider the following pseudocode. A reference to the root of an arbitrary tree represented by the 'leftMostChild-rightSibling' representation is passed as an input to the method DoSomething(). The tree's nodes are all of the treeNode types.
typedef struct treeNode* treeptr;
struct treeNode
{
treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
int value=0;
if (tree != NULL)
{
if (tree->leftMostChild == NULL)
value = 1;
else
value = DoSomething(tree->leftMostChild);
value = value + DoSomething(tree->rightSibling);
}
return(value);
}
When a pointer to a tree's root is supplied as a parameter to DoSomething, the value returned by the function is:
a) The number of leaf nodes present in the tree.
b) The number of internal nodes present in the tree.
c) Height of the tree.
d) The number of nodes without a right sibling in the tree.
Ans. a) The number of leaf nodes present in the tree.
Explanation: The method counts leaf nodes for a tree expressed using the leftMostChild-rightSibling format. The function is shown below, with comments added to show how it works.
int DoSomething(treeptr tree) {
// Base condition when subtree/tree is empty
int value = 0; // IF the tree is not empty
if (tree != NULL) {
// IF this is a leaf node, then initialize value as 1
if (tree->leftMostChild == NULL) value = 1;
// Else initialize value as the value returned by leftmost
// child which in turn calls for the other children of this node
// Using last call "value = value + DoSomething(tree->rightSibling);"
else value = DoSomething(tree->leftMostChild);
// Add value returned by right sibling
value = value + DoSomething(tree->rightSibling);
}
return(value);
}
3. What do the three types of traversals (Inorder, Preorder, and Postorder) have in common?
a) The root is visited before the right subtree
b) The left subtree is always visited before the right subtree
c) The root is visited after the left subtree
d) All of the above
Ans. b) The left subtree is always visited before the right subtree
Explanation: LEFT ROOT RIGHT is the order of inorder traversal. ROOT LEFT RIGHT is the order of preorder traversal. LEFT RIGHT ROOT is the order of postorder traversal. LEFT is explored before RIGHT in all three traversals.
4. For a given binary tree, what does the following function do?
int fun(struct node *root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 0;
return 1 + fun(root->left) + fun(root->right);
}
a) Counts internal nodes
b) Returns height where height is defined as the number of edges on the path from the root to the deepest node
c) Return diameter is the number of edges on the longest path between any two nodes.
d) Counts leaf nodes
Ans. a) Counts internal nodes
Explanation: Internal nodes are counted using this function. It returns 0 if the root is NULL or a leaf node. Otherwise, 1 plus the number of internal nodes in the left subtree plus the number of internal nodes in the right subtree is returned.
5. A queue data structure is used in the following tree traversals?
a) Preorder
b) Inorder
c) Postorder
d) Level order
Ans. d) Level Order
Explanation: To traverse the nodes by level, level order traversal employs a queue data structure.
6. Which of the following cannot yield a complete binary tree?
a) Inorder and Preorder
b) Inorder and Postorder
c) Preorder and Postorder
d) None of the above
Ans. d) None of the above
Explanation: Two traversals are required to build a binary tree, one of which must be in order. On the other hand, preorder and postorder traversals can be used to construct a complete binary tree.
7. The maximum depth or height of a binary tree is calculated by counting the number of nodes along the longest path from the root node to the farthest leaf node with the following function
int maxDepth(struct node* node)
{
if (node == NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return X;
else return Y;
}
}
What should the X and Y values be for the function to perform correctly?
a) X = lDepth, Y = rDepth
b) X = lDepth + 1, Y = rDepth + 1
c) X = lDepth - 1, Y = rDepth -1
d) None of the above
Ans. b) X = lDepth + 1, Y = rDepth + 1
Explanation: The height of a tree is MAX(Height of Left Subtree, Height of Right Subtree) + 1 if it is not empty. See the program Find the Maximum Depth or Height of a Tree for further information.
8. Which tree traversal resembles the graph's breadth-first search?
a) Level order
b) Preorder
c) Inorder
d) Postorder
Ans. a) Level Order
Explanation: The breadth-first search visits all of the neighbors initially, then digs deeper into each one individually. The tree's level order traversal additionally visits nodes on the current level before moving on to the next.
9. What is the worst-case time complexity of adding n2 members into an AVL-tree that originally had n elements?
a) Θ(n4)
b) Θ(n2)
c) Θ(n2 log n)
d) Θ(n3)
Ans. c) Θ(n2 log n)
Explanation: The height of the AVL tree is O(log n), since it is a balanced tree. In the worst scenario, the time complexity of inserting an element into an AVL tree is O(log n). Also see, Insertion in AVL trees.
As n2 element needs to insert into the AVL tree, the total time complexity will be O(n2 log n).
10. A binary tree, T, has a total of 20 leaves. T has a ____ total of nodes with two children.
a) 19
b) 20
c) 21
d) 22
Ans. a) 19
Explanation: If there are N leaf nodes in a binary tree, the number of nodes with two children will be N-1. In this example, the answer will be 20-1, which is 19.
For more Gate questions on tree traversals, refer to our Gate Questions on Tree Traversal: Part 1 and Gate Questions on Tree Traversal: Part 2.