Trees Data Structure PDF 2024/2025

Trees 2024/2025  Tree Data Structure A tree is a non-linear hierarchical data structure that consists of nodes connected by edges. WhyTree Data Structure? Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In or...

Trees 2024/2025  Tree Data Structure A tree is a non-linear hierarchical data structure that consists of nodes connected by edges. WhyTree Data Structure? Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In order to perform any operation in a linear data structure, the time complexity increases with the increase in the data size. But, it is not acceptable in today's computational world. 2  Tree Data Structure: Tree Terminologies Node: A node is an entity that contains a key or value and pointers to its child nodes. Can have 0 or more children. The last nodes of each path are called leaf nodes or external nodes that do not contain a link/pointer to child nodes. The node having at least a child node is called an internal node. Edge: It is the link between any two nodes. Root: It is the top most node of a tree. 3  Tree Data Structure:Tree Terminologies Level /Depth: The level of a node refers to the number of edges on the path from the root to that node. The root node is at level 0, its direct children are at level 1, and so on. Height of a node: The number of edges on the longest path from the node to a leaf node. Height of the tree: The height of the root node, which is the maximum height of all nodes, is the length of the longest path from the root to a leaf node (height of root). 4  Tree Data Structure:Tree Terminologies Subtree: A subtree is a tree that is formed by a node and all its descendants in the tree. Every node in a tree can be considered as the root of its own subtree. Degree of a Node: The degree of a node is the total number of branches of that node, or number of the children. Degree of a Tree: Max degree of all nodes. Size of tree: number of 5 nodes. TreeTraversal: Inorder-Preorder-postorder Linear data structures like arrays, stacks, queues, and linked list have only one way to read the data. But a hierarchical data structure like a tree can be traversed in different ways. According to this structure, every tree is a combination of A node carrying data Two subtrees 6 Inorder traversal 1. First, visit recursively all the nodes in the left subtree 2. Then the root node 3. Visit all the nodes in the right subtree 7  Preorder traversal 1. Visit root node 2. Visit all the nodes in the left subtree 3. Visit all the nodes in the right subtree 8 Postorder traversal 1. Visit all the nodes in the left subtree 2. Visit all the nodes in the right subtree 3. Visit the root node 9  Example 1. Inorder: 12 , 22, 32, 54, 55, 61, 78 2. Preorder: 54, 22, 12, 32, 61, 55, 78 3. Postorder: 12, 32, 22, 55, 78, 61, 54 10  Level Order Traversal Technique is defined as a method to traverse a Tree such that all nodes present in the same level are traversed completely before traversing the next level and in each level from left to rignt. Output: 54, 22, 61, 12, 32, 55, 78 11  Binary Tree A binary tree is a tree data structure in which each parent node can have at most two children. Each node of a binary tree consists of three items: Data item Aaddress of left child Address of right child 12  Binary Tree: Types Types of Binary Tree: In terme of structure or the way nodes are arranged, and in terme of value of nodes: 1. Complete Binary Tree: Every level is fully has exactly two children, except possibly the last may not contain nodes. The nodes at the last level are filled from left to right, with no gaps in between. 13  Binary Tree: Types 2. Full Binary Tree: A full Binary tree is a special type of binary tree in which every parent node has either two or no children. 14  Binary Tree: Types 3. Perfect Binary Tree: A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level. 15  Binary Tree: Types 4. Heap Tree: Must be a complet binary tree, it is either Min Heap or Max Heap. In a Min Binary Heap, the key (value) at the root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap. 16  Binary Tree: Types 5. Binary Search Tree(BST) The properties that separate a binary search tree from a regular binary tree are: All nodes of left subtree are less than the root node All nodes of right subtree are more than the root node Both subtrees of each node are also BSTs i.e. they have the above two previous properties 17  Binary SearchTree Representation A node of a binary tree is represented by a structure (record) containing a data part and two pointers to other structures of the same type. 18 BinarySearchTree Implementation // Declaration 19  BinaryTree Implementation Impty Tree Subtree left node* left (node* A){ int isImpty(node* A){ if (isImpty (A)){ Return A==null; Return null;} Else { return A->left; } } Subtree right node* right (node* A){ if (isImpty (A)){ Return null;} Else { return A ->right; } 20  BinaryTree Operations: Searching Given a BST, the task is to search a node in this BST. For searching a value in BST we can using Binary Search Algorithm. Algorithm to search for a key in a given Binary Search Tree: Let’s say we want to search for the number X, We start at the root. Then: We compare the value to be searched with the value of the root. If it’s equal we are done with the search, if it’s smaller we know that we need to go to the left subtree because in a binary search tree all the elements in the left subtree are smaller and all the elements in the right subtree are larger. Repeat the above step till no more traversal is possible. If at any iteration, key is found, return True. Else False. 21 BinaryTree Operations: Searching BinaryTree Operations: Searching  BinaryTree Operations: Insertion How to Insert a value in a Binary Search Tree: A new key (value) is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node. The below steps are followed while we try to insert a node into a binary search tree: Initilize the current node with root node. Compare the key with the current node. Move left if the key is less than or equal to the current node value, move right if the key is greater than current node value. Repeat steps 2 and 3 until you reach a leaf node. Attach the new node with the key as a left or right child based on the comparison with the 24 leaf node’s value. BinaryTree Operations: Insertion BinaryTree Operations: Insertion BinaryTree Operations: Insertion  BinaryTree Operations: Deletion Case 1. Delete a Leaf Node in BST we are looking for the father of the node to delete,We delete the father-child link. Example: deletion of node 5 28  BinaryTree Operations: Deletion Case 2. Delete a Node with Single Child we search for the father of the node to be deleted, we redirect the father- child link to the (single) child of the node to be deleted. Example: deletion of node 6 29  BinaryTree Operations: Deletion Case 3: Delete a Node with two Children We look for the node of its left branch with the greatest value (or right with the lowest value), as it is the largest (lowest) of this branch. We break the parent-child link, (as in case 2) And we replace the value of the node to be deleted by that (minimum of right or maximum of left) node. Example: deletion of node 11 30