Table of contents
1.
Introduction
2.
Gate Questions on Tree Traversal
3.
Frequently Asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024

Gate Questions on Tree Traversal: Part 3

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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 stackqueue, 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:

  1. 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.
     
  2. 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.
     
  3. 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 InorderPreorderPostorder, 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);
}
You can also try this code with Online C++ Compiler
Run Code

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);
}
You can also try this code with Online C++ Compiler
Run Code


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);
}
You can also try this code with Online C++ Compiler
Run Code

 

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;
    }
}
You can also try this code with Online C++ Compiler
Run Code

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.

Frequently Asked Questions

  1. What is the best approach for traversing a tree?
    Typically, the best optimal algorithm is the one that is tailored to a particular use case and platform.
    Whether you order in advance, preorder, or after makes no difference. Or whether you're a DFS or BFS player.
     
  2. What do you mean by an AVL tree?
    The AVL tree is a self-balancing Binary Search Tree (BST) with a maximum height difference between left and right subtrees of one for all nodes.
     
  3. What are the uses of trees?
    Data with an inherent hierarchical structure can be stored in trees. In its file management system, an operating system may, for example, utilize a tree for directories, files, and folders. They are dynamic, which means that adding and removing nodes is simple.
     
  4. Can we implement Trees with the Standard Template Library?
    The STL tree data structure does not exist since it lacks a "sequence" interface.

Conclusion

In this article, we have extensively discussed the crucial gate questions on tree traversals and some previously asked questions in the gate exam.

Recommended problems -

 

We hope that this blog has helped you enhance your knowledge regarding various gate questions on tree traversal. If you would like to learn more about tree traversals or gate syllabus or questions on stacksqueues, etc., check out our articles on  Coding Ninjas Studio. Do upvote our blog to help other ninjas grow. Happy Coding!

Live masterclass