Tree traversal is a popular form of graph traversal in the world of computer science and data structures, and it is a procedure of visiting each node of the tree. The sequence in which the nodes are visited is prefered to classify these traversals.
As we know, the tree is a non-linear data structure; hence its traversal is not the same as a linear data structure. In the case of linear data structures, we have only a single way to visit each node, and that is to begin from the first element and traverse in a linear order. We have several ways to traverse a tree. In this article, we will learn more about those ways.
Tree traversal is a popular form of graph traversal in the world of computer science and data structures, and it is a procedure of visiting each node of the tree. The sequence in which the nodes are visited is prefered to classify these traversals.
Types of Traversal
Unlike arrays, linked lists, and other linear data structures, tree traversal in the data structure can be performed in a variety of ways. We can search them employing either a depth-first or a breadth-first approach (level order traversal). However, the three most famous techniques are inorder, preorder, and postorder, which come under depth-first traversal.
- Level Order Traversal
- Depth First Traversal
Level Order Traversal
When the nodes of the tree are wrapped in a level-wise mode from left to right, then it represents the level order traversal. We can use a queue data structure to execute a level order traversal.
The below example shows the order of traversing the elements of the tree.
In this case, the level order traversal will give output in the form of the following order: 1, 2, 3, 4, 5, 6, 7.
Depth-First Traversal
When we do a depth-first traversal, we travel in one direction up to the bottom first, then turn around and go the other way. There are three kinds of depth-first traversals.
1. Preorder Traversal
In Preorder, we traverse from the root node to the left subtree and then we proceed to the right subtree.
2. Inorder Traversal
In an inorder traversal, we rather process the left subtree, then move to the root node and then the right subtree.
3. Postorder Traversal
In a postorder, we traverse from the left subtree to the right subtree and then proceed to the root node.
Practice Problems
Q1. The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?
A) 20, 19, 18, 16, 15, 12, 11, 10
B) 10, 11, 12, 15, 16, 18, 19, 20
C) 11, 12, 10, 16, 19, 18, 20,15
D) 19, 16, 18, 20, 11, 12, 10, 15
Q2. Consider the following statements.
S1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S2: The sequence of procedure returns corresponds to a postorder traversal of the activation tree.
Which one of the following options is correct?
Q3. Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr;
Struct treeNode
{
Treeptr leftMostchild, rightSibiling;
};
Int Dosomething (treeptr tree)
{
int value =0;
if (tree ! = NULL) {
If (tree -> leftMostchild = = NULL)
value=1;
else
value = Dosomething (tree->leftMostchild);
value = value + Dosometing (tree->rightsibiling);
}
return (value);
}
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the ________.
Q4. The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.
int height (treeptr n)
{ if (n== NULL) return -1;
if (n-> left == NULL)
if (n-> right ==NULL) return 0;
else return B1 ; // Box 1
else {h1 = height (n -> left);
if (n -> right == NULL) return (1 + h1);
else {h2 = height (n -> right);
return B2 ; // Box 2
}
}
}
The appropriate expression for the two boxes B1 and B2 are _________.
Q5. The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3.
The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.
Your Input ________.
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.
Also Explore,
Comments