Tree Data Structure PDF

Page 1 of 24 TREE DATA STRUCTURE TREE o​ A tree is an ABSTRACT Data type that stores elements hierarchically o​ A data structure that represents a non-linear hierarchical relationship between data elements, called nodes. o​ a set of nodes storing...

Page 1 of 24 TREE DATA STRUCTURE TREE o​ A tree is an ABSTRACT Data type that stores elements hierarchically o​ A data structure that represents a non-linear hierarchical relationship between data elements, called nodes. o​ a set of nodes storing elements such that the nodes have a parent-child relationship PROPERTIES OF TREES o​ There is one and only one path between a pair of nodes in a tree. o​ A tree with n nodes has n-1 edges o​ A graph is a tree if and only if it is minimally connected Source: https://www.geeksforgeeks.org/applications-of-tree-data-structure/ ​ Root: The topmost node in the tree. It has no parent node. ​ Node: A fundamental part of the tree containing data and possibly links to child nodes. ​ Edge: The connection between two nodes. ​ Parent Node: A node that has one or more child nodes. ​ Child Node: A node that descends (has a link) from a parent node. ​ Leaf Node (External Node): A node with no child ​ Subtree: A tree formed by a node and its descendants. ​ Depth: The distance (number of edges) from the root node to a particular node. ​ Height: The distance from a node to the deepest leaf in its subtree. ​ Sibling: Nodes that share the same parent. ​ Degree: the total number of children of a node ​ Internal Node (Non-terminal Nodes): is a node with at least one child; nodes other than leaf nodes;  Page 2 of 24 ​ Level: in a tree each step from top to bottom is called as a Level and the Level count starts with '0' and incremented by one at each level (Step) ​ Path: the sequence of Nodes and Edges from one node to another node. Length of a Path is total number of nodes in that path ​ Sub Tree: In a tree data structure, each child from a node forms a subtree recursively. Every child node will form a subtree on its parent node. Given the following tree: No. of Nodes 11 nodes (N) (A,B,C,D,E,F,G,H,I,J,K) Edges N – 1 = 11 – 1 = 10 edges Root Node A Parent Node A,B,C,E,G Child Nodes B & C are children of A G & H are children of C K is child of G D,E, & F are children of B I & J are children of E Source: http://www.btechsmartclass.com/data_structures/tree- Siblings terminology.html B & C are Siblings D, E & F are Siblings G & H are Siblings I & J are Siblings Leaf Nodes D, I,J, F,K & H Degree Degree of Node B is 3 Degree of Node C is 2 Degree of Node F,I,J,K,H is 0 … The highest degree of a node among all the nodes in a tree is called as 'Degree of Tree' DEGREE OF TREE: 3 Height  Page 3 of 24 In any tree, HEIGHT OF NODE is total number of edges from leaf to that node in longest path. In any tree, HEIGHT OF TREE is the height of the root node. Height of K is 0 Height if the Tree is 3 Depth In any tree, DEPTH OF NODE is total number of edges from root to that node. In any tree, DEPTH OF TREE is the total number of edges from root to leaf in the longest path Depth of A is 0 Depth of the Tree is 3 Level: 3 Path: A-B-E-J has length 4 BINARY TREE o​ is an ordered tree with the following properties: 1. Every node has at most two children. 2. Each child node is labeled as being either a left child or a right child. 3. A left child precedes a right child in the order of children of a node  Page 4 of 24 Source: https://bmsce.ac.in/Content/CS/DS-UNIT-45.pdf o​ level 0 has at most one node (the root), level 1 has at most two nodes (the children of the root), level 2 has at most four nodes, and so on. Note: The maximum number of nodes on the levels of a binary tree grows exponentially TYPES OF BINARY TREE 1. Proper/Full/Strictly Binary Tree: ​ Definition: Every node in the tree has either 0 or 2 children. No node has only one child. ​ Characteristics: o​ All internal nodes have two children. o​ All leaves are at the same level, or the leaves are at the last two levels of the tree.  Page 5 of 24 Source: https://bmsce.ac.in/Content/CS/DS-UNIT-45.pdf Example: An arithmetic expression can be represented by a binary tree whose leaves are associated with variables or constants, and whose internal nodes are associated with one of the operators +, −, ∗, and /, as demonstrated below: A binary tree representing an arithmetic expression. This tree represents the expression ((((3+1) ∗ 3)/((9−5)+2))−((3 ∗ (7−4))+6)). Each node in such a tree has a value associated with it. ✔​ If a node is leaf, then its value is that of its variable or constant. ✔​ If a node is internal, then its value is defined by applying its operation to the values of its children. A typical arithmetic expression tree is a proper binary tree, since each operator +, −, ∗, and / takes exactly two operands. Of course, if we were to allow unary operators, like negation (−), as in “−x,” then we could have an improper binary tree. 2. Perfect/Complete Binary Tree: ​ A binary tree where, 1.​ all internal nodes have two children, and 2.​ all leaf nodes are at the same level.  Page 6 of 24 3. Almost Complete Binary Tree: ​ A binary tree where 1.​ all levels are fully filled except possibly the last level, 2.​ The last level must be strictly filled from left to right. 4. Skewed Binary Tree/Degenerate (or Pathological) Tree: ​ A binary tree where 1.​ All the nodes except one node has one and only one child; and 2.​ The remaining node has no chile 5. Balanced Binary Tree: ​ Definition: A binary tree where the height of the left and right subtrees of any node differs by at most 1. ​ Characteristics: o​ Ensures logarithmic height O(logn). o​ Used to maintain efficient search, insert, and delete operations.  Page 7 of 24 Example: BINARY TREE OUTPUT 1 / \ 2 3 /\ /\ 4 56 7  Page 8 of 24 =============== class TreeNode: def __init__(self, value): self.value = value # Store data in the node self.left = None # Pointer to the left child self.right = None # Pointer to the right child # Recursive method to print the tree (in-order traversal) def print_tree(self, level=0, prefix="Root: "): """ Print the binary tree structure. The method uses recursion to go through the tree and display its structure. """ print(" " * (level * 4) + prefix + str(self.value)) # Print the node's value if self.left: # If left child exists, recursively print it self.left.print_tree(level + 1, "L--- ") if self.right: # If right child exists, recursively print it self.right.print_tree(level + 1, "R--- ") # Creating nodes root = TreeNode(1) # Root node root.left = TreeNode(2) # Left child of root root.right = TreeNode(3) # Right child of root root.left.left = TreeNode(4) # Left child of root.left root.left.right = TreeNode(5) # Right child of root.left root.right.left = TreeNode(6) # Left child of root.right root.right.right = TreeNode(7) # Right child of root.right # Display the tree print("Binary Tree Structure:") root.print_tree() Note: 1.​ TreeNode Class: o​ The TreeNode class represents each node in the binary tree. It stores: ▪​ value: The value of the node. ▪​ left: Pointer/reference to the left child node. ▪​ right: Pointer/reference to the right child node. 2.​ print_tree() Method: o​ This method recursively prints the tree structure. The level parameter controls the depth of the node in the tree, and prefix helps differentiate whether the node is a left or right child. o​ It prints the node's value, and if the node has children, it recursively calls print_tree() on the left and right children with an incremented level. Additional Notes: ​ This visualization approach uses recursive traversal (in-order traversal), which visits the left subtree, prints the current node, and then visits the right subtree. ​ This method prints the tree in a visually indented format, making it easy to see the structure of the tree. IMPLEMENTING TREES a.​ Array-based b.​ Linked-based  Page 9 of 24 Consider: the Tree below: Output: (Array-Based Implementation)  Page 10 of 24 Array-ba sed  Page 11 of 24 ===================================== # Array-Based Implementation of Expression Tree class ArrayExpressionTree: def __init__(self, array): """ Initialize the tree with the given array representation. The array follows a level-order traversal representation of the tree. :param array: List representing the tree in array form. """ self.tree = array def evaluate(self, index=0): """ Recursively evaluate the expression tree. :param index: The current index in the array (default is root at index 0). :return: The result of evaluating the expression tree. """ # If index is out of bounds or the node is None, return 0 (invalid case) if index >= len(self.tree) or self.tree[index] is None: return 0  Page 12 of 24 # If the node is a leaf (operand), return its value if isinstance(self.tree[index], (int, float)): return self.tree[index] # Recursively evaluate the left and right subtrees left_index = 2 * index + 1 # Left child index right_index = 2 * index + 2 # Right child index left_value = self.evaluate(left_index) right_value = self.evaluate(right_index) # Perform the operation represented by the current node if self.tree[index] == '+': return left_value + right_value elif self.tree[index] == '-': return left_value - right_value elif self.tree[index] == '*': return left_value * right_value elif self.tree[index] == '/': return left_value / right_value # Floating-point division def display_tree(self): """ Display the tree structure in a human-readable format. The method uses level-order traversal to show the tree. """ level = 0 count = 0 while count < len(self.tree): num_nodes = 2 ** level nodes = self.tree[count:count + num_nodes] print("Level", level, ":", nodes) count += num_nodes level += 1 # Input Array Representation of the Expression Tree # (((3 + 1) * 4) / ((9 - 5) + 2)) expression_array = [ '/', '*', '+', '+', 4, '-', 2, 3, 1, None, None, 9, 5 ] # Create and use the expression tree expr_tree = ArrayExpressionTree(expression_array) # Display the tree as an array print("Tree as Array:") print("Index: ", list(range(len(expression_array)))) print("Node: ", expression_array) # Display the tree structure print("\nTree Structure:") expr_tree.display_tree() # Evaluate the expression result = expr_tree.evaluate() print("\nThe evaluated result of the expression is:", result)  Page 13 of 24 Output: (Doubly-linked-list Implementation) LINKED-BASE D (Doubly-Linked Node-Based) Page 14 of 24  Page 15 of 24 ====================== class Node: def __init__(self, value): """ Initialize a Node with a value and pointers to left and right children. """ self.value = value # Operator or operand self.left = None # Left child pointer self.right = None # Right child pointer class LinkedExpressionTree: def __init__(self, array): """ Construct the expression tree from the given array representation. :param array: List representing the tree in level-order traversal. """ self.root = self.build_tree(array) def build_tree(self, array): """ Build the tree recursively from the array. :param array: List representation of the tree. :return: Root node of the tree. """ nodes = [Node(value) if value is not None else None for value in array] for i, node in enumerate(nodes): if node is not None: left_index = 2 * i + 1 right_index = 2 * i + 2 if left_index < len(nodes): node.left = nodes[left_index] if right_index < len(nodes): node.right = nodes[right_index] return nodes # Return the root node def evaluate(self, node): """ Recursively evaluate the expression tree. :param node: Current node in the tree. :return: The result of the evaluated expression. """ # If the node is a leaf, return its value if node.left is None and node.right is None: return float(node.value) # Recursively evaluate the left and right subtrees left_value = self.evaluate(node.left) right_value = self.evaluate(node.right) # Apply the operator at the current node if node.value == '+': return left_value + right_value elif node.value == '-': return left_value - right_value elif node.value == '*': return left_value * right_value elif node.value == '/':  Page 16 of 24 return left_value / right_value # Floating-point division def display_tree(self, node, level=0, prefix="Root: "): """ Display the tree structure in a human-readable format. :param node: Current node in the tree. :param level: Current depth level in the tree. :param prefix: Label for the current node. """ if node is not None: print(" " * (4 * level) + prefix + str(node.value)) self.display_tree(node.left, level + 1, "L--- ") self.display_tree(node.right, level + 1, "R--- ") # Input Array Representation of the Expression Tree # (((3 + 1) * 4) / ((9 - 5) + 2)) expression_array = [ '/', '*', '+', '+', 4, '-', 2, 3, 1, None, None, 9, 5 ] # Create and use the linked expression tree expr_tree = LinkedExpressionTree(expression_array) # Display the tree structure print("Tree Structure:") expr_tree.display_tree(expr_tree.root) # Evaluate the expression result = expr_tree.evaluate(expr_tree.root) print("\nThe evaluated result of the expression is:", result) TREE TRAVERSAL o​ A traversal of a tree T is a systematic way of accessing, or “visiting,” all the positions of T. 1.​ Depth-First Traversal 1.1​ In-Order Traversal 1.2​ Pre-Order Traversal 1.3​ Post-Order Traversal 2.​ Breadth-First Traversal Traversal of the tree in data structures is a process of visiting each node and prints their value. There are three ways to traverse tree data structure. DEPTH-FIRST SEARCH TRAVERSAL In-order Traversal Pre-Order Traversal Post-order Traversal (Left, Root Right) (Root, Left, Right) (Left, Right, Root) In the in-order traversal, the left In pre-order traversal, it visits It visits the left subtree first in subtree is visited first, then the the root node first, then the left post-order traversal, then the root, and later the right subtree. subtree, and lastly right subtree. right subtree, and finally the root node. Algorithm: Algorithm: Step 1- Visit all the nodes in the Step 1- Visit root node Algorithm: left subtree Step 2- Visit all the nodes in the Step 1- Visit all the nodes in Step 2- Visit root node left subtree the left subtree  Page 17 of 24 Step 3- Visit all the nodes in the Step 3- Visit all the nodes in the Step 2- Visit all the nodes in right subtree right subtree the right subtree Step 3- Visit the root node Source: P 🡪 Q 🡪 S 🡪 T 🡪 V 🡪 R🡪 U https://byjus.com/gate/tree-traversal-notes / Breadth-First Search (BFS) or Level-Order Traversal In BFS, nodes are visited level Steps: by level, starting from the root 1.​ Visit all nodes at depth 0 and moving downward. (the root). 2.​ Visit all nodes at depth 1 (children of the root). 3.​ Continue visiting nodes level by level. A🡪B🡪C🡪D🡪E🡪F🡪G BINARY SEARCH TREE CONSTRUCTION In a binary search tree (BST), each node contains: – Only smaller values in its left sub tree – Only larger values in its right sub tree  Page 18 of 24 Example: Construct a Binary Search Tree (BST) for the following sequence of numbers: 50, 70, 60, 20, 90, 10, 40, 100  Page 19 of 24 How? When elements are given in a sequence, – Always consider the first element as the root node. – Consider the given elements and insert them in the BST one by one. Page 20 of 24  Page 21 of 24 Source: https://bmsce.ac.in/Content/CS/DS-UNIT-45.pdf Insertion operation The insertion of a new key always takes place as the child of some leaf node. For finding out the suitable leaf node, – Search the key to be inserted from the root node till some leaf node is reached. – Once a leaf node is reached, insert the key as child of that leaf node.  Page 22 of 24 Deletion Operation Deletion Operation is performed to delete a particular element from the Binary Search Tree. When it comes to deleting a node from the binary search tree, three cases are possible Case-01: Deletion Of A Node Having No Child (Leaf Node) Just remove / disconnect the leaf node that is to deleted from the tree. Case-02: Deletion Of A Node Having Only One Child Consider the following example where node with value = 30 is deleted from the BST. Case-03: Deletion Of A Node Having Two Children Consider the following example where node with value = 15 is deleted from the BST Method-1:  Page 23 of 24 a.​ Visit to the right subtree of the deleting node. b.​ Pluck the least value element called as inorder successor. c.​ Replace the deleting element with its inorder successor Method-2: a.​ Visit to the left subtree of the deleting node. b.​ Pluck the greatest value element called as inorder successor. c.​ Replace the deleting element with its inorder successor. Comparison of Traversals Traversal When to Use It Method In-order To process binary search trees (BST) in sorted order. To create a copy of the tree or process root-first operations like evaluating Pre-order expressions. To delete a tree or process child-first operations like calculating disk space in a Post-order directory. Level-order To analyze tree levels or shortest path problems in unweighted trees.  Page 24 of 24 Reference: https://www.pvpsiddhartha.ac.in/dep_it/lecture%20notes/CDS/unit4.pdf https://www.simplilearn.com/tutorials/data-structure-tutorial/trees-in-data-structure Del Tongo, L. (2008). Data Structures and Algorithms (DSA): Annotated Reference with Examples. Retrieved from https://www.mta.ca/~rrosebru/oldcourse/263114/Dsa.pdf