Please help with C++ question in image. Thank you. 2-3- Trees: Create the 2-3 tree with 11 nodes. Also, implement in-order traversal, and findltemfunctions.struct Nodeint small;int large;Node * left;Node* middle;Node* right;}void inorder (Node *tree) ;Node findItem (Node tree, int target);50 9020701201503060(80) (100 110) (130 140)(16040Sample Run:I CAUsers\elee\Desktop\CPSC250-Test\Debug\CPSC250-Test.exePart 1: in-order traversal10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160Part 2: find itemSearch 50Item was found.Search 100Item was found.

unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. Following are the generally used ways for traversing trees. Depth First Traversals: (a) Inorder (Left, Root, Right) : 4 2 5 1 3 (b) Preorder (Root, Left, Right) : 1 2 4 5 3 (c) Postorder (Left, Right, Root) : 4 5 2 3 1Breadth-First or Level Order Traversal: 1 2 3 4 5 Uses of Inorder In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order. To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal s reversed can be used. Example: In order traversal for the above-given figure is 4 2 5 1 3.Inorder Tree Traversal without Recursion Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm. 1) Create an empty stack S. 2) Initialize current node as root 3) Push the current node to S and set current = current->left until current is NULL 4) If current is NULL and stack is not empty then a) Pop the top item from stack. b) Print the popped item, set current = popped_item->right c) Go to step 3. 5) If current is NULL and stack is empty then we are done. 1 / \ 2 3 / \ 4 5 Step 1 Creates an empty stack: S = NULL Step 2 sets current as address of root: current -> 1 Step 3 Pushes the current node and set current = current->left until current is NULL current -> 1 push 1: Stack S -> 1 current -> 2 push 2: Stack S -> 2, 1 current -> 4 push 4: Stack S -> 4, 2, 1 current = NULL Step 4 pops from S a) Pop 4: Stack S -> 2, 1 b) print "4" c) current = NULL /*right of 4 */ and go to step 3 Since current is NULL step 3 doesn't do anything. Step 4 pops again. a) Pop 2: Stack S -> 1 b) print "2" c) current -> 5/*right of 2 */ and go to step 3 Step 3 pushes 5 to stack and makes current NULL Stack S -> 5, 1 current = NULL Step 4 pops from S a) Pop 5: Stack S -> 1 b) print "5" c) current = NULL /*right of 5 */ and go to step 3 Since current is NULL step 3 doesn't do anything Step 4 pops again. a) Pop 1: Stack S -> NULL b) print "1" c) current -> 3 /*right of 1 */ Step 3 pushes 3 to stack and makes current NULL Stack S -> 3 current = NULL Step 4 pops from S a) Pop 3: Stack S -> NULL b) print "3" c) current = NULL /*right of 3 */ Traversal is done now as stack S is empty and current is NULL.JAVA inorder program - // non-recursive java program for inorder traversalimport java.util.Stack; /* Class containing left and right child ofcurrent node and key value*/class Node{ int data; Node left, right; public Node(int item) { data = item; left = right = null; }} /* Class to print the inorder traversal */class BinaryTree{ Node root; void inorder() { if (root == null) return; Stack<Node> s = new Stack<Node>(); Node curr = root; // traverse the tree while (curr != null || s.size() > 0) { /* Reach the left most Node of the curr Node */ while (curr != null) { /* place pointer to a tree node on the stack before traversing the node's left subtree */ s.push(curr); curr = curr.left; } /* Current must be NULL at this point */ curr = s.pop(); System.out.print(curr.data + " "); /* we have visited the node and its left subtree. Now, it's right subtree's turn */ curr = curr.right; } } public static void main(String args[]) { /* creating a binary tree and entering the nodes */ BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.inorder(); }}