4. Apply data structures such as arrays, linked lists, and trees as an abstract concept in problem-solving.

Apply data structures such as arrays, linked lists, and trees as an abstract concept in problem-solving.

1. BER2013 – Algorithm Design & Analysis CLO2:Apply data structures such as arrays, linked lists, and trees as an abstract concept in problem-solving. Binary Tree: • Tree Terminology • Inserting,Traversing and Deleting a node

2. Binary Tree A binary tree is a data structure in which every node or vertex has at most two children. In Python, a binary tree can be represented in different ways with different data structures(dictionary, list) and class representations for a node. However, binarytree library helps to directly implement a binary tree. It also supports heap and binary search tree(BST). This module does not come pre-installed with Python’s standard utility module.

3. Basic Terminology Before we delve deeper into trees, it's essential to familiarize ourselves with some fundamental terms associated with them: Node : A fundamental building block of a tree, representing an element with some associated data. Root : The topmost node in a tree that serves as the starting point to traverse the tree. Parent : A node that has child nodes. Child : Nodes directly connected to a parent node. Leaf : Nodes that do not have any child nodes. Siblings : Nodes that have the same parent. Depth : The depth of a node represents the number of edges from the root to that particular node. Height : The height of a tree is the maximum depth of any node in the tree.

4. Types of Trees Binary Trees A  binary tree  is a specific type of tree structure in which each node can have a maximum of two child nodes. In a binary tree, each node can either have zero, one, or two child nodes. These child nodes are usually referred to as the left child and the right child. Binary Search Trees A  binary search tree (BST)  is a type of binary tree that follows a specific ordering property. In a BST, for each node, all elements in its left subtree are less than the node's value, and all elements in its right subtree are greater than the node's value. This ordering property enables efficient searching, insertion, and deletion operations.

5. Types of Trees AVL Trees An  AVL tree  is a self-balancing binary search tree. It maintains a balanced structure by ensuring that the heights of the left and right subtrees differ by at most one. This self-balancing property reduces the time complexity of search, insertion, and deletion operations, making AVL trees ideal for scenarios where efficient modification operations are required. Red-Black Trees A  red-black tree  is another type of self-balancing binary search tree. It ensures a nearly balanced structure by enforcing additional properties on top of the binary search tree properties. These additional properties involve coloring the nodes as red or black and applying specific rules to maintain the balance.

6. Creating Node The node class represents the structure of a particular node in the binary tree. The attributes of this class are values, left, right. Syntax:   binarytree.Node (value, left=None, right=None) Parameters:   value:  Contains the data for a node. This value must be number.  left: Contains the details of left node child.  right: Contains details of the right node child. Note: If left or right child node is not an instance of binarytree.Node class then binarytree.exceptions.NodeTypeError is raised and if the node value is not a number then binarytree.exceptions.NodeValueError is raised.

7. Example

8. Example

9. Build a Random Binary Tree

10. Insertion in Binary Search Tree(BST) in Python Inserting a node in a Binary search tree involves adding a new node to the tree while maintaining the binary search tree (BST) property. So we need to traverse through all the nodes till we find a leaf node and insert the node as the left or right child based on the value of that leaf node. So the three conditions that we need to check at the leaf node are listed below: Let us insert 13 into the below Binary search tree

11. When we call the insert method then 13 is checked with the root node which is 15 , Since 13 < 15 we need to insert 13 to the left sub tree. So we recursively call left_sub_tree.insert (13) Now the left child of 15 is 10 so 13 is checked with 10 and since 13>10 we need to insert 13 to the right sub tree. So we recursively call right_sub_tree.insert (13) Here, the right child of 10 is 11 so 13 is checked with 11 and since 13>11 and we need to insert 13 to the right child of 11. Again we recursively call right_sub_tree.insert (13) In this recursion call, we found there is no node which means we reached till the leaf node, so we create a node and insert the data in the node

12. Example: class Tree_inserting node.docx

13. Deletion in Binary Search Tree (BST) Given a  BST , the task is to delete a node in this  BST , which can be broken down into 3 scenarios: Case 1. Delete a Leaf Node in BST

14. Case 2. Delete a Node with Single Child in BST Deleting a single child node is also simple in BST.  Copy the child to the node and delete the node . 

15. Case 3. Delete a Node with Both Children in BST Deleting a node with both children is not so simple. Here we have to  delete the node is such a way, that the resulting tree follows the properties of a BST.   The trick is to find the inorder successor of the node. Copy contents of the inorder successor to the node, and delete the inorder successor. Note:   Inorder predecessor can also be used.

16. Implementation of Deletion operation in a BST: Deletion node in BST_Program.docx