Basic Terminologies In Tree Data Structure

Parent Node: The node which is a predecessor of a node is called the parent node of that node. {B} is the parent node of {D, E}.
Child Node: The node that is the immediate successor of a node is called the child node of that node. Examples: {D, E} are the child nodes of {B}.
Root Node: The topmost node of a tree or the node that does not have any parent node is called the root node. {A} is the root node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree.
Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes. {K, L, M, N, O, P, G} are the leaf nodes of the tree.
Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node. {A,B} are the ancestor nodes of the node {E}
Descendant: Any successor node on the path from the leaf node to that node. {E,I} are the descendants of the node {B}.
Sibling: Children of the same parent node are called siblings. {D,E} are called siblings.
Level of a node: The count of edges on the path from the root node to that node. The root node has level 0.
Internal node: A node with at least one child is called Internal Node.
Neighbour of a Node: Parent or child nodes of that node are called neighbors of that node.
Subtree: Any node of the tree along with its descendant.

Tree Traversal Techniques:

1. Inorder Traversal:

Algorithm Inorder(tree)

Traverse the left subtree, i.e., call Inorder(left->subtree)

Visit the root.

Traverse the right subtree, i.e., call Inorder(right->subtree)

In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.

2. Preorder Traversal:

Algorithm Preorder(tree)

Visit the root.

Traverse the left subtree, i.e., call Preorder(left->subtree)

Traverse the right subtree, i.e., call Preorder(right->subtree)

Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expressions on an expression tree.

3. Postorder Traversal:

Algorithm Postorder(tree)

Traverse the left subtree, i.e., call Postorder(left->subtree)

Traverse the right subtree, i.e., call Postorder(right->subtree)

Visit the root

Postorder traversal is used to delete the tree. Postorder traversal is also useful to get the postfix expression of an expression tree

Trees Notes for GATE Exam [2024]Tree Traversal Techniques:

Trees are foundational structures in computer science, serving as the backbone for numerous algorithms and data representations. GATE aspirants should be well versed in tree structures to prepare for the GATE Exam in 2024. This article aims to provide a concise yet comprehensive overview of trees, exploring key concepts crucial for a comprehensive understanding of the topic. To help candidates understand tree-based problem-solving scenarios, these notes provide invaluable insights and knowledge essential to success in GATE.

Table of Content

Introduction to Tree
Basic Terminologies In Tree Data Structure
Types of Tree data structures
Binary Tree
Ternary Tree
N-ary Tree or Generic Tree
Binary Search Tree
AVL Tree
Previously Asked GATE Questions on Trees