algorithm from 2a :

1. Recursive Algorithm for Preorder Traversal

Algorithm recursivePreorderTraversal(BinaryTreeNode root) {

if (root is not null) {

// (i) Visit Root

print root.getData()

// (ii) Visit Left Child

recursivePreorderTraversal(root.getLeftChild())

// (iii) Visit Right Child

recursivePreorderTraversal(root.getRightChild())

}

}

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

sample code BTDriver :

public class BTDriver { public static void main(String[] args) { testBinaryTree(); } public static void testBinaryTree() { BinaryTree dTree = new BinaryTree(); dTree.setTree("D", null, null); BinaryTree fTree = new BinaryTree(); fTree.setTree("F", null, null); BinaryTree gTree = new BinaryTree(); gTree.setTree("G", null, null); BinaryTree hTree = new BinaryTree(); hTree.setTree("H", null, null); // Form larger subtrees BinaryTree eTree = new BinaryTree(); eTree.setTree("E", fTree, gTree); // Subtree rooted at E BinaryTree bTree = new BinaryTree(); bTree.setTree("B", dTree, eTree); // Subtree rooted at B BinaryTree cTree = new BinaryTree(); cTree.setTree("C", null, hTree); // Subtree rooted at C BinaryTree aTree = new BinaryTree(); aTree.setTree("A", bTree, cTree); // Desired tree rooted at A // Display root, height, number of nodes System.out.println("Root of tree contains " + aTree.getRootData()); System.out.println("Height of tree is " + aTree.getHeight()); } }

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