A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. It is widely used in computer science for efficient data storage, retrieval, and manipulation.

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and right child. It is widely used in computer science for efficient data storage, retrieval, and manipulation.

1. MODULE-2 Data Structures

2. UNIT-1 8L+8T+8P=24 Hours TREES Trees: Basic Terminology, Types of Trees, Binary Tree – Introduction, properties, array and linked representations; Tree traversals and their implementation; Expression trees; BST – definition and operations, AVL trees – definition and construction; Applications of binary trees. UNIT-2 8L+8T+8P=24 Hours GRAPHS & HASHING Graphs: Basic Terminology, Types of Graphs, Graphs representations – adjacency matric, adjacency list; Traversals - breath first search and depth first search; Applications of graphs. Hashing: Introduction, Different hash functions, collision: avoidance and handling methods.

3. UNIT-1 Trees

4. Tree In linear data structure data is organized in sequential order and in non-linear data structure data is organized in random order. A tree is a very popular non-linear data structure used in a wide range of applications. A tree data structure can be defined as follows... Tree is a non-linear data structure that organizes data in a hierarchical structure and this is a recursive definition.

5. A tree data structure can also be defined as follows... Tree data structure is a collection of data (Node) which is organized in hierarchical structure recursively In tree data structure, every individual element is called as  Node . Node in a tree data structure stores the actual data of that particular element and link to next element in hierarchical structure. In a tree data structure, if we have  N  number of nodes then we can have a maximum of  N-1  number of links.

6. Example

7. Terminology In a tree data structure, we use the following terminology... 1. Root In a tree data structure, the first node is called as  Root Node . Every tree must have a root node. We can say that the root node is the origin of the tree data structure. In any tree, there must be only one root node. We never have multiple root nodes in a tree .

8. 2. Edge In a tree data structure, the connecting link between any two nodes is called as  EDGE . In a tree with ' N ' number of nodes there will be a maximum of ' N-1 ' number of edges.

9. 3. Parent In a tree data structure, the node which is a predecessor of any node is called as  PARENT NODE . In simple words, the node which has a branch from it to any other node is called a parent node. Parent node can also be defined as " The node which has child / children ".

10. 4. Child In a tree data structure, the node which is descendant of any node is called as  CHILD Node . In simple words, the node which has a link from its parent node is called as child node. In a tree, any parent node can have any number of child nodes. In a tree, all the nodes except root are child nodes.

11. 5. Siblings In a tree data structure, nodes which belong to same Parent are called as  SIBLINGS . In simple words, the nodes with the same parent are called Sibling nodes.

12. 6. Leaf In a tree data structure, the node which does not have a child is called as  LEAF Node . In simple words, a leaf is a node with no child. In a tree data structure, the leaf nodes are also called as  External Nodes . External node is also a node with no child. In a tree,  leaf node is also called as ' Terminal ' node.

13. 7. Internal Nodes In a tree data structure, the node which has atleast one child is called as  INTERNAL Node . In simple words, an internal node is a node with atleast one child. In a tree data structure, nodes other than leaf nodes are called as  Internal Nodes .  The root node is also said to be Internal Node  if the tree has more than one node.  Internal nodes are also called as ' Non-Terminal ' nodes.

14. 8 . Degree In a tree data structure, the total number of children of a node is called as  DEGREE  of that Node. In simple words, the Degree of a node is total number of children it has. The highest degree of a node among all the nodes in a tree is called as ' Degree of Tree '

15. 9. Level In a tree data structure, the root node is said to be at Level 0 and the children of root node are at Level 1 and the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple words, 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).

16. 10. Height In a tree data structure, the total number of edges from leaf node to a particular node in the longest path is called as  HEIGHT  of that Node.  In a tree, height of the root node is said to be  height of the tree . In a tree,  height of all leaf nodes is '0'.

17. 11. Depth In a tree data structure, the total number of egdes from root node to a particular node is called as  DEPTH  of that Node.  In a tree, the total number of edges from root node to a leaf node in the longest path is said to be  Depth of the tree . In simple words, the highest depth of any leaf node in a tree is said to be depth of that tree. In a tree,  depth of the root node is '0'.

18. 12. Path In a tree data structure, the sequence of Nodes and Edges from one node to another node is called as  PATH  between that two Nodes.  Length of a Path  is total number of nodes in that path.  In below example  the path A - B - E - J has length 4 .

19. 13. 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.

20. Binary Tree In a normal tree, every node can have any number of children. A binary tree is a special type of tree data structure in which every node can have a  maximum of 2 children . One is known as a left child and the other is known as right child. A tree in which every node can have a maximum of two children is called Binary Tree.

21. In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than 2 children . Example

22. There are different types of binary trees and they are ... 1. Strictly Binary Tree In a binary tree, every node can have a maximum of two children. But in strictly binary tree, every node should have exactly two children or none. That means every internal node must have exactly two children. A strictly Binary Tree can be defined as follows... A binary tree in which every node has either two or zero number of children is called Strictly Binary Tree Strictly binary tree is also called as  Full Binary Tree  or  Proper Binary Tree  or  2-Tree

23. Strictly binary tree data structure is used to represent mathematical expressions. Example

24. 2. Complete Binary Tree In a binary tree, every node can have a maximum of two children. But in strictly binary tree, every node should have exactly two children or none and in complete binary tree all the nodes must have exactly two children and at every level of complete binary tree there must be 2 level  number of nodes. For example at level 2 there must be 2 2  = 4 nodes and at level 3 there must be 2 3  = 8 nodes. A binary tree in which every internal node has exactly two children and all leaf nodes are at same level is called Complete Binary Tree.

25. Complete binary tree is also called as  Perfect Binary Tree

26. 3. Extended Binary Tree A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes wherever required. The full binary tree obtained by adding dummy nodes to a binary tree is called as Extended Binary Tree.

27. Binary Tree Representations A binary tree data structure is represented using two methods. Those methods are as follows... Array Representation Linked List Representation Consider the following binary tree...

28. 1. Array Representation of Binary Tree In array representation of a binary tree, we use one-dimensional array (1-D Array) to represent a binary tree. Consider the above example of a binary tree and it is represented as follows... To represent a binary tree of depth  'n'  using array representation, we need one dimensional array with a maximum size of  2n + 1 .

29. 2. Linked List Representation of Binary Tree We use a double linked list to represent a binary tree. In a double linked list, every node consists of three fields. First field for storing left child address, second for storing actual data and third for storing right child address. In this linked list representation, a node has the following structure...

30. 2. Linked List Representation of Binary Tree We use a double linked list to represent a binary tree. In a double linked list, every node consists of three fields. First field for storing left child address, second for storing actual data and third for storing right child address. In this linked list representation, a node has the following structure ... The above example of the binary tree represented using Linked list representation is shown as follows...

31. Binary Tree Traversals: The process of visiting all the nodes of a tree atleast once is called tree traversal Unlike linear data structures in which the elements are traversed sequentially, tree is a nonlinear data structure in which the elements can be traversed in many different ways Three different algorithms are used for tree traversals Pre-Order In-Order Post-Order

32. Pre Order Traversal To traverse a non-empty binary tree in pre-order, the following operations are performed recursively at each node Visit the root node Traverse the left sub-tree Traverse the right sub-tree . Algorithm: PREORDER(TREE ) Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: Write TREE ->DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END

33. In-order Traversal To traverse a non-empty binary tree in in-order, the following operations are performed recursively at each node Traverse the left sub-tree Visit the root node Traverse the right sub-tree Algorithm: INORDER(TREE) Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: INORDER(TREE -> LEFT) Step 3: Write TREE -> DATA Step 4: INORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END

34. Post order Traversal To traverse a non-empty binary tree in post-order, the following operations are performed recursively at each node Traverse the left sub-tree Traverse the right sub-tree Visit the root node Algorithm: POSTORDER(TREE) Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: POSTORDER(TREE -> LEFT) Step 3: POSTORDER(TREE -> RIGHT) Step 4: Write TREE->DATA [END OF LOOP] Step 5: END

35. Example1: Pre-order, In-order, Post-order Traversal

36. Example2: Pre-order-In-order-Post-order Traversal

37. Example3: Pre-order, In-order, Post-order Traversal IN ORDER TRAVERSAL: I - D - J - B - F - A - G - K - C - H PRE-ORDER TRAVERSAL: A - B - D - I - J - F - C - G - K - H POST-ORDER TRAVERSAL: I - J - D - F - B - K - G - H - C - A

38. Example4: Pre-order, In-order, Post-order Traversal IN ORDER TRAVERSAL: 5 , 15 , 18 , 20 , 25 , 30 , 35 , 40 , 45 , 50 , 60 PRE-ORDER TRAVERSAL: 30 , 20 , 15 , 5 , 18 , 25 , 40 , 35 , 50 , 45 , 60 POST-ORDER TRAVERSAL: 5 , 18 , 15 , 25 , 20 , 35 , 45 , 60 , 50 , 40 , 30

39. Binary Tree Traversals When we wanted to display a binary tree, we need to follow some order in which all the nodes of that binary tree must be displayed. In any binary tree, displaying order of nodes depends on the traversal method. Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal. There are three types of binary tree traversals. In - Order Traversal Pre - Order Traversal Post - Order Traversal Consider the following binary tree...

40. Properties of Binary Tree 1) Each node should have atmost 2 children. 2) Max number of nodes possible at any level 'n' is 2 n 3) Max number of nodes of height h = 2 h+1 -1 4) Min number of nodes of height h= h+1

41. Implementation of Binary Tree using DLL /*Main Function*/ int main() { node *root; root=create(); } /*Structure of node*/ struct node { int data; struct node *left; struct node *right; }; /*Node Creation*/ struct node *create() { struct node *new; int x; new=(struct node*) malloc ( sizeof (struct node)); printf ("Enter data(-1 for no data):"); scanf ("% d",&x ); if(x==-1) { return NULL; } new->data=x; printf ("Enter left child of %d:\ n",x ); new->left=create(); printf ("Enter right child of %d:\ n",x ); new->right=create(); return new; }

42. Implementation of Binary Tree Traversals using DLL /*Main Function*/ int main() { struct node *root; printf ("pre order is:"); preorder (root); inorder (root); postorder (root); } /*PRE ORDER*/ void preorder ( struct node * root) { if(root==NULL) { return; } printf ("%d", root->data); preorder (root->left); preorder (root->right); }

43. Implementation of Binary Tree Traversals using DLL /*IN ORDER */ void inorder ( struct node * root) { if(root==NULL) { return; } inorder (root->left); printf ("%d", root->data); inorder (root->right); } /*POST ORDER*/ void postorder ( struct node * root) { if(root==NULL) { return; } postorder (root->left); postorder (root->right); printf ("%d", root->data); }

44. Construction of Expression Tree Expression tree is a binary tree, because all of the operations are binary. It is also possible for a node to have only one child. The leaves of an expression tree are operands, such as constants or variable names, and the other (non leaf) nodes contain operators. Once an expression tree is constructed we can traverse it in three ways: • Inorder Traversal • Preorder Traversal • Postorder Traversal An expression tree can be generated for the infix and postfix expressions .

45. Examples of Expression Tress

46. Steps to construct Expression Tree 1) Convert the given infix expression to post fix expression 2) An algorithm to convert a postfix expression into an expression tree is as follows : Read the expression one symbol at a time. If the symbol is an operand, we create a one-node tree and push a pointer to it onto a stack. If the symbol is an operator, we pop pointers to two trees T1 and T2 from the stack (T1 is popped first) and form a new tree whose root is the operator and whose left and right children point to T2 and T1 respectively. A pointer to this new tree is then pushed onto the stack . 3) Repeat this process until all the characters are read from postfix expression.

47. Examples: Expression: A+B Post fix Expression: AB+ 2) Expression: (A+B)*(C-D) Post fix Expression: AB+CD-* 3) Expression: A+B*C/D Post fix Expression: ABC*D/

48. Expression : (A + B * C) – ((D * E + F) / G) Post fix Expression: A B C * + D E * F + G / -

49. 5) Post fix Expression: a b + c d e + * * For the above tree: Inorder form of the expression: a + b * c * d + e Preorder form of the expression: * + a b * c + d e Postorder form of the expression: a b + c d e + * *

50. Threaded Binary Tree Binary Tree is represented using linked list representation. A node doesn’t have a child is filled with NULL Pointer. There are number of NULL pointers than actual pointers. This NULL pointer does not play any role except indicating that their is no link. If there are n number of nodes then their n+1 NULL pointers are present.

51. Binary trees have a lot of wasted space: the leaf nodes each have 2 null pointers We can use these pointers to help us in inorder traversals We have the pointers reference the next node in an inorder traversal; called threads We need to know if a pointer is an actual link or a thread, so we keep a boolean for each pointer

52. Threaded Binary T ree is also a binary tree in which all left child pointers that are NULL points to its in-order predecessor. All right child pointers that are NULL points to its i9n-order successor. If there is no in-order predecessor or in-order successor then it points to the root node.

53. Binary Search Trees

54. A Binary Search Tree , also known as an ordered binary tree , is a variant of binary trees in which the nodes are arranged in an order. A binary search tree is a binary tree with the following properties : The left sub-tree of a node N contains values that are less than N’s value. The right sub-tree of a node N contains values that are greater than N’s value. Both the left and the right binary trees also satisfy these.

55. Binary Search Tree

56. Create a binary search tree using the following data elements: 45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81

57. Create a binary search tree using the following data elements: 45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81

58. Operations on Binary Search Trees Different operations van be performed on Binary search tree Inserting a new node in a binary search tree Deleting a node from a binary search tree Searching an element in a binary search tree

59. Inserting a new node in a binary search tree To insert an element find the correct position where the insertion has to be done and then add the node at that position.

60. Inserting a new node in a binary search tree Inserting node 12 for the tree

61. Deleting a node from a binary search tree We will take up three cases in this section and discuss how a node is deleted from a binary search tree. Case 1: Deleting a Node that has No Children Case 2: Deleting a Node with One Child Case 3: Deleting a Node with Two Children

62. Case 1: Deleting a Node that has No Children Look at the binary search tree given in Fig . If we have to delete node 78, we can simply remove this node without any issue. Deleting node 78 from the given binary search tree

63. Case 2: Deleting a Node with One Child To handle this case, the node’s child is set as the child of the node’s parent. In other words, replace the node with its child. Now, if the node is the left child of its parent, the node’s child becomes the left child of the node’s parent. Correspondingly , if the node is the right child of its parent, the node’s child becomes the right child of the node’s parent.

64. Look at the binary search tree shown in Fig. Deleting node 54 from a binary search tree

65. Case 3: Deleting a Node with Two Children To handle this case, replace the node’s value with its in-order predecessor (largest value in the left sub-tree) or in-order successor (smallest value in the right sub-tree ). The in-order predecessor or the successor can then be deleted using any of the above cases.

66. Look at the binary search tree given in Fig Deleting node 56 from the given binary search tree and replacing a node with maximum element from the left sub tree

67. Deleting node 56 from the given binary search tree and replacing a node with minimum element from the right sub tree

68. Algorithm

69. Searching an element in a binary search tree The searching process begins at the root node . The function first checks if the binary search tree is empty . If it is empty, then the value we are searching for is not present in the tree . However , if there are nodes in the tree , then the search function checks to see if the key value of the current node is equal to the value to be searched . If not, it checks if the value to be searched for is less than the value of the current node, in which case it should be recursively called on the left child node. In case the value is greater than the value of the current node, it should be recursively called on the right child node

70. Algorithm

71. Searching a node with value 67 in the given binary search tree

72. Binary Search Tree

73. Example: Construct BST by inserting 25,10,12,15,39,64,53, and then delete 15, 10, and insert 45, 23, and 30. also Find Pre-order, in order and post order traversals Construct BST by inserting 10,12,5,4,20,8,7,15 and 13 and then delete 20,4 and 10

74. AVL TREE Adelson- Veleski and Landis

75. An AVL tree is defined as follows ... An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of every node is either -1, 0 or +1.

76. Balance factor Balance factor of a node is the difference between the heights of the left and right subtrees of that node. The balance factor of a node is calculated either  height of left subtree - height of right subtree  (OR)  height of right subtree - height of left subtree . In the following explanation, we calculate as follows ... Balance factor = heightOfLeftSubtree - heightOfRightSubtree

77. Example of AVL Tree Every AVL Tree is a binary search tree but every Binary Search Tree need not be AVL tree.

78. AVL Tree Rotations In AVL tree, after performing operations like insertion and deletion we need to check the  balance factor  of every node in the tree. If every node satisfies the balance factor condition then we conclude the operation otherwise we must make it balanced. Whenever the tree becomes imbalanced due to any operation we use  rotation  operations to make the tree balanced. Rotation is the process of moving nodes either to left or to right to make the tree balanced .

79. There are  four  rotations and they are classified into  two  types.

80. Single Left Rotation (LL Rotation) In LL Rotation, every node moves one position to left from the current position. To understand LL Rotation, let us consider the following insertion operation in AVL Tree ...

81. Single Right Rotation (RR Rotation) In RR Rotation, every node moves one position to right from the current position. To understand RR Rotation, let us consider the following insertion operation in AVL Tree ...

82. Left Right Rotation (LR Rotation) The LR Rotation is a sequence of single left rotation followed by a single right rotation. In LR Rotation, at first, every node moves one position to the left and one position to right from the current position. To understand LR Rotation, let us consider the following insertion operation in AVL Tree...

83. Right Left Rotation (RL Rotation) The RL Rotation is sequence of single right rotation followed by single left rotation. In RL Rotation, at first every node moves one position to right and one position to left from the current position. To understand RL Rotation, let us consider the following insertion operation in AVL Tree...

84. Operations on an AVL Tree The following operations are performed on AVL tree... Search Insertion Deletion

85. Searching

86. AVL TREE INSERTION TreeNode * insertRecursive ( TreeNode *r, TreeNode * new_node ) 1. IF r==NULL THEN -> 1.1. r= new_node 1.2. return r 2. IF new_node ->value LESS THAN r->value THEN -> 2.1. r->left = insert(r->left, new_node ) 3. ELSE IF new_node ->value GREATER THAN r->value THEN -> 3.1. r->right = insert(r->right, new_node ) 4. ELSE 4.1. PRINT("No duplicate values") 4.2. return r

87. 5. bf = getBalanceFactor (r) 6 . IF bf > 1 AND new_node ->value < r->left->value 6.1. return rightRotate (r) 7 . IF bf < -1 & new_node ->value > r->right->value 7.1. return leftRotate (r) 8 . IF bf > 1 & new_node ->value > r->left->value 8.1. r->left = leftRotate (r->left) 8.2. return rightRotate (r) 9 . IF bf < -1 & new_node ->value < r->right->value 9.1. r->right = rightRotate (r->right) 9.2. return leftRotate (r) 10 . return r

88. Balance Factor int getBalanceFactor ( TreeNode *n) { 1. IF (n == NULL) 1.1. return -1; 2. ELSE 2.1. return (height(n->left) - height(n->right)); }

89. Right Rotate TreeNode * rightRotate ( TreeNode *y) { TreeNode *x = y->left; TreeNode *T2 = x->right; // Perform rotation x->right = y; y->left = T2; return x; }

90. Left Rotate TreeNode * LefrRotate ( TreeNode *x) { TreeNode *y = x->right; TreeNode *T2 = y->left; // Perform rotation y- >left = x ; x->right = T2; return y; }

91. AVL Tree Deletion

92. Application of Binary Trees: Search algorithms:  Binary search algorithms use the structure of binary trees to efficiently search for a specific element. The search can be performed in O(log n) time complexity, where n is the number of nodes in the tree. Sorting algorithms:  Binary trees can be used to implement efficient sorting algorithms, such as binary search tree sort. Database systems:  Binary trees can be used to store data in a database system, with each node representing a record. This allows for efficient search operations and enables the database system to handle large amounts of data . File systems:  Binary trees can be used to implement file systems, where each node represents a directory or file. This allows for efficient navigation and searching of the file system.

93. Decision trees:  Binary trees can be used to implement decision trees, a type of machine learning algorithm used for classification and regression analysis.

94. Game AI : Binary trees can be used to implement game AI, where each node represents a possible move in the game. The AI algorithm can search the tree to find the best possible move . Routing Tables: A routing table is used to link routers in a network. It is usually implemented with a tree data structure, which is a variation of a binary tree.  The tree data structure will store the location of routers based on their IP addresses. Routers with similar addresses are grouped under a single subtree . Real-time applications of Binary Trees: DOM in HTML. File explorer. Used as the basic data structure in Microsoft Excel and spreadsheets. Editor tool: Microsoft Excel and spreadsheets. Evaluate an expression Routing Algorithms

95. Advantages of Binary Tree: Efficient searching : Binary trees are particularly efficient when searching for a specific element, as each node has at most two child nodes, allowing for binary search algorithms to be used. This means that search operations can be performed in O(log n) time complexity. Ordered traversal:  The structure of binary trees enables them to be traversed in a specific order, such as in-order, pre-order, and post-order. This allows for operations to be performed on the nodes in a specific order, such as printing the nodes in sorted order. Memory efficient : Compared to other tree structures, binary trees are relatively memory-efficient because they only require two child pointers per node. This means that they can be used to store large amounts of data in memory while still maintaining efficient search operations. Fast insertion and deletion:  Binary trees can be used to perform insertions and deletions in O(log n) time complexity. This makes them a good choice for applications that require dynamic data structures, such as database systems. Easy to implement:  Binary trees are relatively easy to implement and understand, making them a popular choice for a wide range of applications. Useful for sorting:  Binary trees can be used to implement efficient sorting algorithms, such as heap sort and binary search tree sort.

96. Disadvantages of Binary Tree: Limited structure : Binary trees are limited to two child nodes per node, which can limit their usefulness in certain applications. For example, if a tree requires more than two child nodes per node, a different tree structure may be more suitable. Unbalanced trees : Unbalanced binary trees, where one subtree is significantly larger than the other, can lead to inefficient search operations. This can occur if the tree is not properly balanced or if data is inserted in a non-random order. Space inefficiency : Binary trees can be space inefficient when compared to other data structures. This is because each node requires two child pointers, which can be a significant amount of memory overhead for large trees. Slow performance in worst-case scenarios : In the worst-case scenario, a binary tree can become degenerate, meaning that each node has only one child. In this case, search operations can degrade to O(n) time complexity, where n is the number of nodes in the tree. Complex balancing algorithms : To ensure that binary trees remain balanced, various balancing algorithms can be used, such as AVL trees and red-black trees. These algorithms can be complex to implement and require additional overhead, making them less suitable for some applications.