Welcome to Lesson 11!Learning ObjectivesBy the end of today's class, you should know...How to trace recursive tree traversals on a BST:inOrderpreOrderpostOrderHow to write the above 3 methodsHow the method call stack is used to produce the correct output1. Tree Traversals1.1 Tree Traversal IntroductionTraversals define an ordering for which we can "visit" each element in a structure to perform operations such as printing.With linear structures, such as a linked lists, the order in which to visit each value is evident.However, for trees, there is no obvious ordering of the nodes.There are many possible ways to visit each node in a BST.We will examine 3 options:pre orderpost orderin orderIn your Lab, you will be asked to write preOrderPrint, inOrderPrint and postOrderPrint, which each define a means of printing BSTs according to the ordering defined by the traversals.These recursive methods are simple to write.Their names come from when the root of each subtree is visted.Is it visited before the recursive calls (preorder)?Is it visited after the recursive calls (postorder)?Is it visited between the recursive calls (inorder)?What do you think the Big-O runtime of these methods is?O(n) Why?Let's get an introduction to this topic by watching this videoBelow is the pseudocode for each of the methods.Note that these methods would be the "helper" versions in our implementationPseudocode for inOrderPrint(root)1. If the root is NULL    a. return;2. Otherwise    a. Call inOrderPrint recursively on the root's leftchild    b. Print the data at the root    c. Call inOrderPrint recursively on the root's rightchildPseudocode for preOrderPrint(root)1. If the root is NULL    a. return2. Otherwise    a. Print the data at the root    b. Call preOrderPrint recursively on the root's leftchild    c. Call preOrderPrint recursively on the root's rightchildPseudocode for postOrderPrint(root)1. If the root is NULL    a. return2. Otherwise    a. Call postOrderPrint recursively on the root's leftchild    b. Call postOrderPrint recursively on the root's rightchild    c. Print the data at the root1.2. Tree Traversal ExamplesLet's trace the printing order of the three algorithms on the same binary treeinOrderPrint: preOrderPrint: postOrderPrint: Image sources1.3. Reflection: Tracing Tree Traversals and Writing the MethodsFind a piece of paperUsing the examples above, trace inOrderPrint, preOrderPrint and postOrderPrint on the BST below.Now, write the 3 recursive print methods, along with their helper methods.Wrap UpAnswer the review questions on Canvas for today's lesson~Have a Great Day!~