Binary Tree Traversal MethodsSlide 2Preorder TraversalPreorder Example (visit = print)Slide 5Preorder Of Expression TreeInorder TraversalInorder Example (visit = print)Slide 9Inorder By Projection (Squishing)Inorder Of Expression TreePostorder TraversalPostorder Example (visit = print)Slide 14Postorder Of Expression TreeTraversal ApplicationsLevel OrderLevel-Order Example (visit = print)Binary Tree ConstructionSome ExamplesSlide 21Preorder And PostorderInorder And PreorderSlide 24Slide 25Inorder And PostorderInorder And Level OrderBinary Tree Traversal Methods•In a traversal of a binary tree, each element of the binary tree is visited exactly once.•During the visit of an element, all action (make a clone, display, evaluate the operator, etc.) with respect to this element is taken.Binary Tree Traversal Methods•Preorder•Inorder•Postorder•Level orderPreorder Traversalpublic static void preOrder(BinaryTreeNode t){ if (t != null) { visit(t); preOrder(t.leftChild); preOrder(t.rightChild); }}Preorder Example (visit = print)ab ca b cPreorder Example (visit = print)ab cdefgh ija b d g h e i c f jPreorder Of Expression Tree+ab-cd+ef*/Gives prefix form of expression!/ * + a b - c d + e fInorder Traversalpublic static void inOrder(BinaryTreeNode t){ if (t != null) { inOrder(t.leftChild); visit(t); inOrder(t.rightChild); }}Inorder Example (visit = print)ab cb a cInorder Example (visit = print)ab cdefgh ijg d h b e i a f j cInorder By Projection (Squishing)ab cdefgh ijg d h b e i afj cInorder Of Expression Tree+ab-cd+ef*/Gives infix form of expression (sans parentheses)!ea + b * c d / + f-Postorder Traversalpublic static void postOrder(BinaryTreeNode t){ if (t != null) { postOrder(t.leftChild); postOrder(t.rightChild); visit(t); }}Postorder Example (visit = print)ab cb c aPostorder Example (visit = print)ab cdefgh ijg h d i e b j f c aPostorder Of Expression Tree+ab-cd+ef*/Gives postfix form of expression!a b + c d - * e f + /Traversal Applicationsab cdefgh ij• Make a clone.• Determine height.•Determine number of nodes.Level OrderLet t be the tree root.while (t != null){ visit t and put its children on a FIFO queue; remove a node from the FIFO queue and call it t; // remove returns null when queue is empty}Level-Order Example (visit = print)ab cdefgh ija b c d e f g h i jBinary Tree Construction•Suppose that the elements in a binary tree are distinct.•Can you construct the binary tree from which a given traversal sequence came?•When a traversal sequence has more than one element, the binary tree is not uniquely defined.•Therefore, the tree from which the sequence was obtained cannot be reconstructed uniquely.Some Examplespreorder = abababinorder = abbaabpostorder = abbabalevel order = abababBinary Tree Construction•Can you construct the binary tree, given two traversal sequences?•Depends on which two sequences are given.Preorder And Postorderpreorder = abababpostorder = ba• Preorder and postorder do not uniquely define a binary tree.• Nor do preorder and level order (same example).• Nor do postorder and level order (same example).Inorder And Preorder•inorder = g d h b e i a f j c•preorder = a b d g h e i c f j•Scan the preorder left to right using the inorder to separate left and right subtrees.•a is the root of the tree; gdhbei are in the left subtree; fjc are in the right subtree.agdhbei fjcInorder And Preorder•preorder = a b d g h e i c f j•b is the next root; gdh are in the left subtree; ei are in the right subtree.agdhbei fjcagdhfjcbeiInorder And Preorder•preorder = a b d g h e i c f j•d is the next root; g is in the left subtree; h is in the right subtree.agdhfjcbeiagfjcbeidhInorder And Postorder•Scan postorder from right to left using inorder to separate left and right subtrees.• inorder = g d h b e i a f j c• postorder = g h d i e b j f c a•Tree root is a; gdhbei are in left subtree; fjc are in right subtree.Inorder And Level Order•Scan level order from left to right using inorder to separate left and right subtrees.• inorder = g d h b e i a f j c• level order = a b c d e f g h i j•Tree root is a; gdhbei are in left subtree; fjc are in right