Binary Trees 2PowerPoint PresentationSlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11PostorderSlide 13Slide 14ExampleAbout level orderSlide 17Slide 18Slide 19Slide 20Sample tree to illustrate tree traversalTree after four nodes visited in preorder traversalTree after left subtree of root visited using preorder traversalTree after completed preorder traversalTree visited using inorder traversalTree visited using postorder traversalSlide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Binary Trees 2Prof. Sin-Min LeeDepartment of Computer ScienceFor each number of nodes, n, there is a certain number of possible binary tree configurations. These numbers form a sequence of integers with respect to n. A useful way to describe an integer sequence is to construct a generating function: whose coefficients bi are the sequence. B(x) is power series over a purely formal variable x.Apparently, b1 is 1, and b2 is 2. The b0 coefficient is somewhat artificial, its the no-nodes tree which is, I guess, the only one. Further analysis gives the following idea: if a binary tree has n nodes, then there must be one node as the root and two subtrees. The total number of nodes in the subtrees must be n-1, and either of them may be empty. Assuming k nodes in the left subtree, the right subtree then has n-k-1 nodes, k going from 0 to n-1. The root node is always there, and therefore the tree configurations differ only by the configuration of subtrees.The total number of possible trees on n nodes can then be expressed as:PostorderTemplate <class T>void Postorder ( BinaryTreeNode<T> *t){ // Postorder traversal of *t. If (t){ Postorder ( t->LeftChild);//do left subtree Postorder(t->RightChild);//do right subtree visit(t); // visit tree root }}Each root is visited after its left and right subtrees have been traversed.ExamplePreorder +*ab/cdInorder a*b+c/dPostorder ab*cd/+Elements of a binary tree listed in pre-,in-,and postorder.+b*/dcaAbout level orderWhile loop only if the tree is not emptyFollowing the addition of the children of t to the queue,we attempt to delete an element from the queue. If the queue is empty,Delete throws an OutOfBounds exception. If the queue is not empty,then Delete returns the deleted element in t.Sample tree to illustrate tree traversal12 351048 9611 127Tree after four nodes visited in preorder traversal12 351048 9611 1271234Tree after left subtree of root visited using preorder traversal12 351048 9611 1271234657Tree after completed preorder traversal12 351048 9611 127123465789101112Tree visited using inorder traversal12 351048 9611 1277421 3561198 1012Tree visited using postorder traversal12 351048 9611 12712631 2541197 810Here we will work through an example showing how a preorder traversal can be obtained by explicit use of a stack. The logicfollows (see the text for the code): 1.Stack the root node. 2.Exit with completion if the stack is empty. 3.Pop the stack and visit the node obtained. 4.Push the right child, if it exists, on the stack. 5.Push the left child, if it exists, on the stack. 6.Go to 2.Using the runtime stack via recursion, we can write simple definitions of the three depth-first traversals without use of an explicitstack (in these definitions I leave out the templates for brevity): void Preorder(TreeNode *p) { if (p) { Visit(p); Preorder(p->left); Preorder(p->right); }}void Inorder(TreeNode *p) { if (p) { Inorder(p->left); Visit(p); Inorder(p->right); }}void Postorder(TreeNode *p) { if (p) { Postorder(p->left); Postorder(p->right); Visit(p); }}TREE SORTCombines tree initialization, insertion, and inorder traversal to generate and print each node in a "sorted" binary tree.1. Initialize: read first item, create root node.2. For each item after the first: read item and insert in tree.3. Traverse in order, printing each node.More formally, in pseudocode:def treesort () read item root = makebt(null, item, null) while not end of data read item insert(root, item) end while inorder(root)endUsing tree sort, sort the letters M, A, R, J, K, S, V.Insertion produces M / \ A R \ \ J S \ \ K VTraverse in order => A J K M R S