05-Jan-19 TREE INTRODUCTION QA tree is non-linear data structure used to store information. Qt is a hierarchical data structure which differentiates from stacks & queues (linear data structures). QA tree is connected, acyclic graph A connected / acyclic graph [TREE] TREE INTRODUCTION OA tree is so connected that any node in the graph can be reached from any other node by exactly one path. QA tree does not contain any closed path. QO Consider the following ROOTED TREE (i.e. A tree which has only single root node which has no parents).05-Jan-19 TREE wos = ANT en HERE, A is Root Node [ Which has no Parent Node]. B, D are known as Interior Nodes and C, E, F, G are known as Leaf nodes TREE DIFFERENT CATEGORIES OF TREE Balanced Binary TreeTREE BASIC TERMINOLOGIES OF TREE ROOT : This is the one of the main component of tree. A node without parent is known as root. In diagram, A is root node. CIBRANCH : This is also one of the main component of tree, Branching factor defines the maximum number of children to any node. So, if a branching factor of 2 means Binary Tree. Edge : A finite collection of directed arcs that connect pair of nodes. In short, link between two nodes, O The direction from root to leaves is ‘DOWN’ and the opposite direction is UP’ CICLIMBING TREE means going from leaves to the root. (2 DESCENDING TREE means going from root to the leaves. CUNULL TREE means tree with no nodes. TREE BASIC TERMINOLOGIES OF TREE: CULEAF NODE: A node that has no children is called a leaf node. It is also known as terminal nodes and rest of the nodes are known as non-terminal nodes. GINTERIOR NODE: Nodes which possess children are called the interior nodes. QSIBLINGS : All the nodes of the same parent node are called siblings (Brother) CIDEGREE OF NODE : The number of the sub-trees of a node is called the degree of the node. A node with degree 0 is called leaf node. Ol DEPTH OR HEIGHT OF TREE : Length of the longest path from root to any node is known as depth or height of the tree. (The nodes which are at the same level are said to be of the same generation. 05-Jan-1905-Jan-19 ueveto @ e evel TREE _f v In this diagram, 1 is root / node as it has no parent node. 8 v 4,7,8,9 have no / branches which is known as QO Leaf Nodes. v¥ Aand5arechildrenof2 Vv The nodes 1, 2, 3, while 2 is parent of 4and5. 5, 6 have a branch v As4and 5 has the to other nodes, so common parent 2, they are they are known as known as Siblings. Non-Leaf Nodes.05-Jan-19 TREE 8 vin this diagram, 2 is left a oe sub-tree of root 1 and 3 is, right sub-tree of root 1. 8 v Similarly, node 4 is left sub-tree of node 2 and 5 is right sub-tree of node 2. oO eo 0° Y All the nodes you can reach from a v Every node which _ is parent to leaf and non-leaf node is known as given node are ANCESTOR. known as DESCENDANT. TREE 8 v In this diagram, 1 is ancestafy 3) of node 5 and 8 is descendant \ of node 3. ‘9 e Y Node 5 is neither an ancetor \ nor a descendant of node 3. \ Oo eo 9 v In this diagram, 1 is @ depth / height 0, 2 and 3 is @ depth / height 1. v Similarly, 4, 5, 6 are @ depth / height 2 and so on.BINARY TREE - DEFINITION There are different ways to define binary tree. Among these some of as are under: Q Every nodes in a tree has a maximum of two children are known as Binary Tree. OR We can say that every node of a tree can have at most degree 2 is known as binary tree. QA binary tree is a finite set of elements that is either empty or divides into three disjoint subsets. The first subset contains a single element called a root, and the other two subsets are left and right sub-trees. QA tree in which every root has either one or two nodes is called binary tree. The Left part of root is known as left sub-tree and right part of root is known as right sub-tree. BINARY TREE - DEFINITION Following figure shows possible binary trees with three nodes. ROOT ROOT @ ROOT RooT ROOT @ ® e 05-Jan-1905-Jan-19 Generate Binary Tree for 10,3,20,2,7,5,15,31 The binary tree creation follows a simple principle to add new node to the tree. > It compares the new value with the current element of the tree. > if its value is less than the current element in the tree then it will move towards the left side of the tree. > And if its value is greater than the current element in the tree then it will move towards the right side of the tree. BINARY TREE - CONCEPT Q In this diagram, 10 is root node as it does not have any parent node. 02,5, 15, 31 are leaf nodes as they have no children. O The binary tree creation follows a simple/principle to add new node to the tree. eo Ge C1 It compares the new value with the current elément of the tree. @ Qif its value is less than the current element in the tree then it will move towards the left side of the tree. (And if its value is greater than the current element in the tree then it will move towards the right side of the tree.05-Jan-19 LINKED LIST REPRESENTATION OF BINARY TREE DATA | RIGHT RIGHT SUB - TREE ROOT LEFT SUB - TREE tla ey Meche DATA | RIGHT \ \ coc ona) mcr LEAVES DEPTH / LEVEL OF BINARY TREE / oO i e perma uve 0 ea,2° ©05-Jan-19 DEPENDING ON THE DEPTH / LEVEL OF BINARY TREE, IT CAN BE CLASSIFIED AS: 1. STRICTLY BINARY TREE: If every non-leaf node in a binary tree has exactly two non-empty children (left and right sub tree) then it is known as Strictly Binary Tree. That means, strictly binary tree with n leaves will always have 2n-1 nodes. Every node in this type of tree can have either no child or two children. Strictly Binary Tree also known as 2-Tree or Extended These types of trees are generally used to represent any expression with binary operation. [And so it is also said to be EXPRESSION TREE] DEPENDING ON THE DEPTH / LEVEL OF BINARY TREE, IT CAN BE CLASSIFIED AS: Consider Expression E=(a+b)/((c-d) *e) EXPRESSION oo05-Jan-19 DEPENDING ON THE DEPTH / LEVEL OF BINARY TREE, IT CAN BE CLASSIFIED AS: 2. COMPLETE BINARY TREE: * If all the leaves of strictly binary tree are at the same depth / level then it is said to be complete binary tree. 1 © © 900 12 23 14 15 DEPENDING ON THE DEPTH / LEVEL OF BINARY TREE, IT CAN BE CLASSIFIED AS: 2. COMPLETE BINARY TREE: * The main advantage of this type of tree is we can easily search the left and right sub tree of any node. In this type, if we want to find out the parent of particular child then any node N will be at floor(N/2). For example, if want to find parent of node O then floor(15/2) = 7, ie. G. Similarly, if we want to find out left and right sub-tree of any Node then evaluate 2N and 2N + 1 respectively. For Example, Left sub-tree of Node G is N [2N = 2*7 = 14) and Right sub-tree of Node G is O [2N + 1= 2*7 + 1= 15] 1005-Jan-19 DEPENDING ON THE DEPTH / LEVEL OF BINARY TREE, IT CAN BE CLASSIFIED. 3. ALMOST COMPLETE BINARY TREE: * A binary tree of depth / level ‘d’ is known as almost complete binary tree if each node in the tree is either at level d ord—1. LINKED LIST REPRESENTATION POINTER TO LEFT. amen cne SUB-TREE (LEFT Reece EE (RIGHT. CHILD NODE) CHILD NODE) As above mentioned in diagram we have three members for structure while working with linked list representation of trees. [Left Pointer — DATA — Right Pointer] struct node { int data; struct node *left_tree; struct node *right_tree; k 1.