Discrete Structure - Binary Trees PDF

DISCRETE STRUCTURE Binary Trees: If the outdegree of every node is less than or equal to 2, in a directed tree than the tree is called a binary tree. A tree consisting of the nodes (empty tree) is also a binary tree. (0,1,2) Basic Terminology: Root: A binary tree has a unique node called the...

DISCRETE STRUCTURE Binary Trees: If the outdegree of every node is less than or equal to 2, in a directed tree than the tree is called a binary tree. A tree consisting of the nodes (empty tree) is also a binary tree. (0,1,2) Basic Terminology: Root: A binary tree has a unique node called the root of the tree. Left Child: The node to the left of the root is called its left child. Right Child: The node to the right of the root is called its right child. Parent: A node having a left child or right child or both are called the parent of the nodes. Siblings: Two nodes having the same parent are called siblings. Leaf: A node with no children is called a leaf. The number of leaves in a binary tree can vary from one (minimum) to Descendant: A node is called descendant of another node if it is the child of the node or child of some other descendant of that node. All the nodes in the tree are descendants of the root. Left Subtree: The subtree whose root is the left child of some node is called the left subtree of that node. Example: For the tree as shown in fig: Which node is the root? Which nodes are leaves? Name the parent node of each node Solution: (i) The node A is the root node. (ii) The nodes G, H, I, L, M, N, O are leaves. (iii) Nodes Parent B, C A D, E B F C G, H D I, J E K F Right Subtree: The subtree whose root is the right child of some node is called the right subtree of that node. Level of a Node: The level of a node is its distance from the root. The level of root is defined as zero. The level of all other nodes is one more than its parent node. The maximum number of nodes at any level N is 2N. Depth or Height of a tree: The depth or height of a tree is defined as the maximum number of nodes in a branch of a tree. This is more than the maximum level of the tree, i.e., the depth of root is one. The maximum number of nodes in a binary tree of depth d is 2d-1, where d ≥1. External Nodes: The nodes which have no children are called external nodes or terminal nodes. Internal Nodes: The nodes which have one or more than one children are called internal nodes or non-terminal nodes Binary Expression Trees: An algebraic expression can be conveniently expressed by its expression tree. An expression having binary operators can be decomposed into (operator) Depending upon precedence of evaluation. The expression tree is a binary tree whose root contains the operator and whose left subtree contains the left expression, and right subtree contains the right expression. Example: Construct the binary expression tree for the expression (a+b)*(d/c) Solution: The binary expression tree for the expression (a+b)*(d/c) is shown in fig  Complete Binary Tree: Complete binary tree is a binary tree if it is all levels, except possibly the last, have the maximum number of possible nodes as for left as possible. The depth of the complete binary tree having n nodes is log2 n+1. ample: The tree shown in fig is a complete binar ee. Full Binary Tree: Full binary tree is a binary tree in which all the leaves are on the same level and every non-leaf node has two children. fferentiate between General Tree and Binary Tree General Tree Binary Tree 1. There is no such tree 1. There may be an having zero nodes or an empty binary tree. empty general tree. 2. If some node has a 2. If some node has a child, then there is no child, then it is such distinction. distinguished as a left child or a right child. 3. The trees shown in fig are distinct, when we 3. The trees shown in fig consider them as binary Traversing Binary Trees Traversing means to visit all the nodes of the tree. There are three standard methods to traverse the binary trees. These are as follows: 1.Preorder Traversal 2.Postorder Traversal 1. Preorder Traversal: The preorder traversal of a binary tree is a recursive process. The preorder traversal of a tree is Visit the root of the tree. Traverse the left subtree in preorder. 2. Postorder Traversal: The postorder traversal of a binary tree is a recursive process. The postorder traversal of a tree is Traverse the left subtree in postorder. Traverse the right subtree in postorder. Visit the root of the tree. 3. Inorder Traversal: The inorder traversal of a binary tree is a recursive process. The inorder traversal of a tree is  Traverse in inorder the left subtree. Visit the root of the tree. Traverse in inorder the right subtree. Example: Determine the preorder, postorder and inorder traversal of the binary tree as shown in fig: Solution: The preorder, postorder and inorder traversal of the tree is as follows: Preorde 1 2 3 4 5 6 7 8 9 10 11 r Postorder 3 5 4 2 7 10 9 11 8 6 1 Inorder 3 2 5 4 1 7 6 9 10 8 11 Algorithms: (a)Algorithm to draw a Unique Binary Tree when Inorder and Preorder Traversal of the tree is Given: 1.We know that the root of the binary tree is the first node in its preorder. Draw the root of the tree. 2.To find the left child of the root node, first, use the inorder traversal to find the nodes in the left subtree of the binary tree. (All the nodes that are left to the root node in the inorder traversal are the nodes of the left 1.In the same way, use the inorder traversal to find the nodes in the right subtree of the binary tree. Then the right child is obtained by selecting the first node in the preorder traversal of the right subtree. Draw the right child. 2.Repeat the steps 2 and 3 with each new node until every node is not visited in the preorder. Finally, we obtain a unique tree. Example: Draw the unique binary tree when the inorder and preorder traversal is given as follows: Inorde B A D C F E J H K G I r Preor A B C D E F G H J K I der Solution: We know that the root of the binary tree is the first node in preorder traversal. Now, check A, in the inorder traversal, all the nodes that are of left A, are nodes of left subtree and all the nodes that are right of A, are nodes of right subtree. Read the next node in the preorder and check its position against the root node, if its left of the root node, then draw it as a left child, otherwise draw it a right child. Repeat the above process for each new node until all the nodes of the preorder traversal are read and finally (b) Algorithm to draw a Unique Binary Tree when Inorder and Postorder Traversal of the tree is Given: 1.We know that the root of the binary tree is the last node in its postorder. Draw the root of the tree. 2.To find the right child of the root node, first, use the inorder traversal to find the nodes in the right subtree of the binary tree. (All the nodes that are right to the root node in the inorder traversal are the nodes of the right subtree). After that, the right child of the root is obtained by selecting the last node in the postorder traversal of the right 3. In the same way, use the inorder traversal to find the nodes in the left subtree of the binary tree. Then the left child is obtained by selecting the last node in the postorder traversal of the left subtree. Draw the left child. 4. Repeat the steps 2 and 3 with each new node until every node is not visited in the postorder. After visiting the last node, we  Example: Draw the unique binary tree for the given Inorder and Postorder traversal is given as follows: Inorder 1 1 1 1 4 6 8 2 1 5 7 9 3 0 2 1 3 Postorder 1 1 1 1 8 6 4 2 9 7 5 3 1 2 0 3 1 Solution: We know that the root of the binary tree is the last node in the postorder traversal. Hence, one in the root node Now, check the inorder traversal, we know that root is at the center, hence all the nodes that are left to the root node in inorder traversal are the nodes of left subtree and, all that are right to the root node are the nodes of the right subtree. Now, visit the next node from back in postorder traversal and check its position in inorder traversal, if it is on the left of root then draw it as left child and if it is on the right, then draw it as the right child. Repeat the above process for each new node, and (c)Algorithm to convert General Tree into the binary tree 1.Starting from the root node, the root of the tree is also the root of the binary tree. 2.The first child C1(from left) of the root node in the tree is the left child C1 of the root node in the binary tree, and the sibling of the C1 is the right child of C1 and so on. 3.Repeat the step2 for each new node