Creating a Tree-Traversal [100 pts] (a) Refer to the topic of traversing nodes of a tree. We had discussed several ways of traversing (node visitation) of a tree, such as inorder, postorder, preorder, levelorder. You can use push and pop node(s) of a tree on a stack as a means to create a traversal order

(b) Refer to Figure 25-5 of the textbook that walks through the process that uses a stack to create an iterative inorder traversal of a binary tree, using a while loop. The section also shows Java method that implements the following algorithm to generate an inorder traversal of a binary tree with root as treeRoot

Algorithm doInorderTraversal(BinaryTreeNode treeRoot) {

Create Stack nodeStack = new Stack(); Set CurrentNode = treeRoot;

While(nodeStack notEmpty || currentNode is not null) { While(currentNode is not null) {

push current node on stack

currentNode = left child of current node }

// end inner while

If(nodeStack notEmpty) {

pop nodeStack and call it nextNode

print nextNode

set currentNode to right child of nextNode

} // end if

} // end outer while }

// end algorithm

(c) In this assignment, you will create preordertraversal sequence in two ways, one by using a stack object and second by a recursive method. Both ways should generate the same preordersequence of nodes of tree

Note: Recursive definition of preordertraversal (node visitation) is as follows: - Visit Root - Visit Left Child - Visit Right Child

2. Pre-Lab Planning

(a) Based on the note above, write recursive algorithm for preordertraversal of a binary tree. The format for the algorithm should be similar to 1(b) above. Refer to the diagrammatic process flow to create a preorder traversal of a binary tree as shown in Figure 25-6(a) of textbook to define the algorithm [20 pts]

(b) Load the Tree Sample Code, shared in Canvas after class session on ADT Tree

(c) Refer to the BinaryTree class in the sample code loaded in 2(b)

Sample code :

package com.mycompany.treesamplecode; /** A class that implements the ADT binary tree. */ public class BinaryTree implements BinaryTreeInterface { private BinaryTreeNode root; public BinaryTree() { root = null; } // end default constructor public BinaryTree(T rootData) { root = new BinaryTreeNode(rootData); } // end constructor public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { initializeTree(rootData, leftTree, rightTree); } // end constructor public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { initializeTree(rootData, (BinaryTree)leftTree, (BinaryTree)rightTree); } // end setTree public void setRootData(T rootData) { root.setData(rootData); } // end setRootData public T getRootData() { if (isEmpty()) throw new EmptyTreeException(); else return root.getData(); } // end getRootData public boolean isEmpty() { return root == null; } // end isEmpty public void clear() { root = null; } // end clear public int getHeight() { int height = 0; if (root != null) height = root.getHeight(); return height; } // end getHeight protected void setRootNode(BinaryTreeNode rootNode) { root = rootNode; } // end setRootNode protected BinaryTreeNode getRootNode() { return root; } // end getRootNode private void initializeTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryTreeNode(rootData); if ((leftTree != null) && !leftTree.isEmpty()) root.setLeftChild(leftTree.root); if ((rightTree != null) && !rightTree.isEmpty()) { if (rightTree != leftTree) root.setRightChild(rightTree.root); else root.setRightChild(rightTree.root.copy()); } // end if if ((leftTree != null) && (leftTree != this)) leftTree.clear(); if ((rightTree != null) && (rightTree != this)) rightTree.clear(); } // end initializeTree /** BinaryTreeNode inner class used by the BinaryTree class. */ class BinaryTreeNode { private T data; private BinaryTreeNode leftChild; // Reference to left child private BinaryTreeNode rightChild; // Reference to right child public BinaryTreeNode() { this(null); // Call next constructor } // end default constructor public BinaryTreeNode(T dataPortion) { this(dataPortion, null, null); // Call next constructor } // end constructor public BinaryTreeNode(T dataPortion, BinaryTreeNode newLeftChild, BinaryTreeNode newRightChild) { data = dataPortion; leftChild = newLeftChild; rightChild = newRightChild; } // end constructor /** Retrieves the data portion of this node. @return The object in the data portion of the node. */ public T getData() { return data; } // end getData /** Sets the data portion of this node. @param newData The data object. */ public void setData(T newData) { data = newData; } // end setData /** Retrieves the left child of this node. @return A reference to this node's left child. */ public BinaryTreeNode getLeftChild() { return leftChild; } // end getLeftChild /** Sets this nodes left child to a given node. @param newLeftChild A node that will be the left child. */ public void setLeftChild(BinaryTreeNode newLeftChild) { leftChild = newLeftChild; } // end setLeftChild /** Detects whether this node has a left child. @return True if the node has a left child. */ public boolean hasLeftChild() { return leftChild != null; } // end hasLeftChild /** Retrieves the right child of this node. @return A reference to this node's right child. */ public BinaryTreeNode getRightChild() { return rightChild; } // end getRightChild /** Sets this nodes right child to a given node. @param newRightChild A node that will be the right child. */ public void setRightChild(BinaryTreeNode newRightChild) { rightChild = newRightChild; } // end setRightChild /** Detects whether this node has a right child. @return True if the node has a right child. */ public boolean hasRightChild() { return rightChild != null; } // end hasRightChild /** Detects whether this node is a leaf. @return True if the node is a leaf. */ public boolean isLeaf() { return (leftChild == null) && (rightChild == null); } // end isLeaf /** Computes the height of the subtree rooted at this node. @return The height of the subtree rooted at this node. */ public int getHeight() { return getHeight(this); } // end getHeight public BinaryTreeNode copy() { BinaryTreeNode newRoot = new BinaryTreeNode(data); if (leftChild != null) newRoot.setLeftChild(leftChild.copy()); if (rightChild != null) newRoot.setRightChild(rightChild.copy()); return newRoot; } // end copy private int getHeight(BinaryTreeNode node) { int height = 0; if (node != null) height = 1 + Math.max(getHeight(node.getLeftChild()), getHeight(node.getRightChild())); return height; } // end getHeight } // end BinaryTreeNode } // end BinaryTree

3. Writing Code (a) Since before you start to generate any traversal of a tree, that tree will have to be created first, the testBinaryTree() method of the BTDriver class in the Sample Code has been created for you, which you will need to run to build the tree. You will need to update testBinaryTree () method so it builds the following binary tree

For example, to build the subtree shown in the dotted square above, your code should be as follows:

BinaryTree leftSubTree = new BinaryTree(); leftSubTree.setTree("1", null, null);

BinaryTree rightSubTree = new BinaryTree(); rightSubTree.setTree("8", null, null);

BinaryTree subTree = new BinaryTree(); subTree.setTree("4", leftSubTree, rightSubTree);

Based on the algorithm you will have created in 2(a) above, write a recursive method recursivePreorderTraversal(root) that generates a preordertraversal of nodes of a binary tree, shown in the diagram in 3(a), such that [40 pts]

(i) This method must be called recursively (call itself)

(ii) The initial call of this method should be provided the root node of the tree as method argument

(iii) The final output of the method should be a string that shows tree data in preorder format

Note: - As discussed in class, each node of the binary tree will be a BinaryTreeNode object. Review structure of class BinaryTreeNode which is the inner class of BinaryTree. It has 3 attributes, data, leftChild and rightChild. You will be printing data attribute of each node you visit in a binary tree traversal - If a node does not have either right child, left child or both, the respective attribute value(s) will be null

Please answer all parts and put full code for the questions that require it and algorithm for the parts that require it