Data Structure Unit 4 Notes

• Tree Data Structure
• Tree Terminology
• Binary Tree
• Complete Binary Tree
• Full Binary Tree
• Binary Tree Representation
• Tree Traversal
• Preorder Traversal
• Inorder Traversal
• Postorder Traversal
• Level Order Traversal
• Binary Search Tree
• BST Insertion
• BST Searching
• BST Deletion
• Threaded Binary Tree
• AVL Tree
• Tree Rotations
• B Tree
• B+ Tree

Data Structure Unit 4 mainly deals with tree data structures and their advanced concepts. A tree is a non-linear data structure used to store data in a hierarchical form. In a linear data structure like array, stack, queue or linked list, data is arranged one after another. But in a tree, data is arranged in the form of parent and child relationships. This makes trees very useful for representing real-world hierarchical information such as family trees, file systems, organization charts, website menus and database indexes.

The most important reason for studying trees is efficiency. When data becomes large, simple linear searching may take more time. A properly arranged tree can reduce searching time and make insertion, deletion and retrieval faster. For example, in a Binary Search Tree, smaller values are stored on the left side and greater values are stored on the right side. Because of this rule, the searching process becomes more systematic than checking every element one by one.

In this unit, students first learn basic tree terminology such as root, node, edge, parent, child, sibling, leaf node, degree, level, height and depth. These terms are necessary because most exam questions require correct use of tree vocabulary. After that, Binary Tree is studied. A Binary Tree is a special tree in which each node can have at most two children. These children are called left child and right child. Binary Tree is the foundation for many advanced trees.

Tree traversal is another highly important topic. Traversal means visiting every node of a tree in a specific order. The common traversal techniques are preorder, inorder, postorder and level order traversal. In preorder traversal, the root is visited first, then the left subtree and then the right subtree. In inorder traversal, the left subtree is visited first, then root and then right subtree. In postorder traversal, the left subtree and right subtree are visited before the root. Level order traversal visits nodes level by level from top to bottom.

Binary Search Tree, commonly known as BST, is one of the most exam-important parts of this unit. A BST follows an ordered structure. For every node, all values in the left subtree are smaller than the node value and all values in the right subtree are greater than the node value. This property helps in faster searching and sorting. RGPV exams often ask students to construct a BST from a given sequence of numbers and then perform inorder, preorder or postorder traversal.

Students also study advanced trees such as Threaded Binary Tree, AVL Tree, B Tree and B+ Tree. Threaded Binary Tree uses empty child links to store traversal-related information, which helps in faster traversal without using stack or recursion. AVL Tree is a self-balancing Binary Search Tree. Whenever insertion or deletion makes the tree unbalanced, rotations are performed to balance it again. B Tree and B+ Tree are used in database systems and file systems because they are efficient for storing large data on disk.

From an RGPV exam point of view, Unit 4 is very scoring because many questions are diagram-based and procedure-based. Students should practice drawing trees neatly, writing traversal output correctly and explaining operations step by step. Topics like BST construction, AVL rotations and B+ Tree concepts should not be ignored because they are commonly asked in both short-answer and long-answer formats.

A tree contains nodes connected by edges. The first and topmost node of the tree is called the root node. A node that has no child is called a leaf node or terminal node. Nodes that have at least one child are called internal nodes. The connection between two nodes is called an edge. The number of edges on the longest path from root to a leaf is generally called the height of the tree. These definitions look small, but they are very important for writing correct answers in exams.

A Binary Tree can be represented in memory using linked representation or array representation. In linked representation, each node contains three parts: data, address of left child and address of right child. This is the most common representation because it supports dynamic memory allocation. In array representation, nodes are stored according to their position. If a node is stored at index i, then its left child may be stored at 2i and right child at 2i + 1 in one-based indexing. Array representation is useful for complete binary trees but may waste memory for sparse trees.

Tree traversal is used when we want to process each node of a tree. Traversal is not only important for exams but also important in real programming. For example, expression trees are used in compilers to evaluate mathematical expressions. File systems use tree traversal to list files and folders. Search engines and artificial intelligence systems also use tree-like structures for decision making and indexing.

Inorder traversal of a Binary Search Tree produces sorted output. This is a very important point. For example, if a BST is created using values 50, 30, 70, 20, 40, 60 and 80, then inorder traversal gives 20, 30, 40, 50, 60, 70, 80. This property is frequently used in exam questions. Students should always remember that inorder traversal of BST gives ascending order.

Insertion in a BST starts from the root node. If the new value is smaller than the current node, we move to the left child. If the new value is greater than the current node, we move to the right child. This process continues until an empty position is found. Searching also follows the same logic. Deletion in BST is slightly more complex because there are three cases: deleting a leaf node, deleting a node with one child and deleting a node with two children. For a node with two children, inorder successor or inorder predecessor is generally used.

AVL Tree solves the problem of an unbalanced BST. If values are inserted in sorted order into a normal BST, the tree may become skewed and performance becomes similar to a linked list. AVL Tree maintains balance factor for each node. Balance factor is calculated as height of left subtree minus height of right subtree. If the balance factor becomes less than -1 or greater than +1, rotations are applied. The four common AVL rotation cases are LL rotation, RR rotation, LR rotation and RL rotation.

B Tree and B+ Tree are multiway search trees. They are mainly used when data is too large to fit completely in main memory. Database indexing systems use B Tree and B+ Tree because they reduce disk access and keep data sorted. In a B Tree, keys and records may be stored in internal nodes as well as leaf nodes. In a B+ Tree, actual records are generally stored at leaf level, and leaf nodes are connected with each other for faster range searching. This is why B+ Tree is widely used in database management systems.

For Unit 4, students should not only read definitions but also practice drawing trees. Many answers become strong when supported by a neat diagram. In tree questions, presentation matters a lot. Always start with a short definition, then draw a diagram, explain terminology and finally write advantages or applications if required.

For traversal questions, practice at least ten different examples. A common mistake is mixing preorder, inorder and postorder rules. Remember simple order: preorder means Root Left Right, inorder means Left Root Right and postorder means Left Right Root. Write these formulas in rough work before solving the question.

For BST questions, insert values one by one carefully. Do not rearrange values randomly. Compare every new value with the root and then move left or right according to BST property. After creating the tree, check whether all left values are smaller and all right values are greater. This small checking step can prevent mistakes.

For AVL Tree, focus on balance factor and rotation cases. Many students lose marks because they identify the wrong rotation. LL and RR are single rotations, while LR and RL are double rotations. Draw each step clearly. Even if the final tree is correct, unclear steps may reduce marks in university exams.

For B Tree and B+ Tree, focus more on concepts, properties and differences rather than complex numerical construction unless your teacher has specifically practiced it in class. These topics are often asked as theory questions, short notes or comparison questions.