This seems strangely familiar. Create a binary search tree but with an array imp
ID: 3678480 • Letter: T
Question
This seems strangely familiar. Create a binary search tree but with an array implementation. The data contained in this tree is positive integers, so it may help to initialize the entire tree as some negative sentinel value (like -1)s to indicate that certain values have not been populated. Download the driver file, in order to test it out.
The class IntBSTree is given fill in the following methods
insert: This method returns nothing and takes in an integer value that is then placed as a new node in the tree based on the binary tree properties. A reminder values greater than the parent go to the right subtree and values smaller go to the left subtree. Also it may be a good idea to use a recursive method in order to place these values.
printInorder: This method which returns nothing and has no parameters prints the in order traversal of the tree. For in order traversal each left subtree must be visited, then the value is printed out, and finally each of the right subtrees is visited. It is a good idea to make a recursive method to assist with this. Also if done correctly in-order traversals print out each of the integers in ascending order.
printBreadthOrder: This method which returns nothing and has no parameters prints the breadth order traversal of the tree. For this one each element in a row (in other words it and all of its siblings) are printed from left to right.
getDepth: The depth of a node is the number of edges from the root to that number. This method returns the depth and takes in a parameter corresponding to the integer value of a node whose depth is returned. If the value is not in the tree a -1 should be returned. Again a recursive helper method may be useful to solve this.
Driver File:
File:
Int BST Tester!
Creating tree
Populating Tree with values
Testing insertion by in-order traversal
1
2
3
4
5
6
7
8
9
10
Testing breadth order traversal
4
2
8
1
3
7
10
5
9
6
Getting depth of 6
4
Getting depth of 14
-1
Explanation / Answer
Solution: See the code below:
1. IntBSTree class: In InBSTree.java
---------------------------------------------
package intbst;
import java.util.LinkedList;
import java.util.Queue;
/**
* IntBSTree class
*
*/
public class IntBSTree {
private class Node {
private int data;
private Node leftChild;
private Node rightChild;
public Node(int aData) {
this.data = aData;
this.leftChild = null;
this.rightChild = null;
}
}
private Node root;
// traverses a given tree/subtree with node as root in inorder
private void printInorder(Node node) {
if (node != null) {
printInorder(node.leftChild); // traversal of left subtree
System.out.println(node.data); // visits the node
printInorder(node.rightChild); // traversal of right subtree
}
}
// traverses a given tree/subtree with node as root in breadth order
private void printBreadthOrder(Node node) {
Queue<Node> queue = new LinkedList<Node>(); // queue to hold nodes at a
// given level
// breadth order traversal of tree
while (node != null) {
System.out.println(node.data); // visits node
// adds left child to queue, if not null
if (node.leftChild != null)
queue.add(node.leftChild);
// adds left child to queue, if not null
if (node.rightChild != null)
queue.add(node.rightChild);
// checks if queue is empty before removing a node
if (queue.isEmpty())
return;
// removes the node from queue to visit
node = (Node) queue.remove();
}
}
private int getDepth(Node node, int value, int depth) {
if (node != null) {
if (value == node.data)
return depth; // Found
else if (value < node.data) {
depth++;
return getDepth(node.leftChild, value, depth);
} else {
depth++;
return getDepth(node.rightChild, value, depth);
}
}
return -1;
}
// Constructor
public IntBSTree() {
root = null;
}
// inserts a new node with a given data
public void insert(int data) {
Node p = root, prev = null; // prev keeps track of parent node
// insertion of node
if (root == null) // if tree is empty
{
root = new Node(data);
return;
} else {
// finds place for new node, if tree not empty
while (p != null) {
prev = p;
if (p.data > data)
p = p.leftChild;
else
p = p.rightChild;
}
if (prev.data > data)
prev.leftChild = new Node(data);
else if (prev.data < data)
prev.rightChild = new Node(data);
}
}
// Inorder traversal of tree
public void printInorder() {
printInorder(root);
}
// gets depth of a given value in tree, if present
public int getDepth(int value) {
return getDepth(root, value, 0);
}
// Breadth order traversal of tree
public void printBreadthOrder() {
printBreadthOrder(root);
}
}
-----------------------------------------------------
2. IntBSTreeTester class: In IntBSTreeTester.java
-------------------------------------------------
package intbst;
/**
* IntBSTreeTester class
*
*/
public class IntBSTreeTester {
public static void main(String[] args) {
System.out.println("Int BST Tester!");
System.out.println("Creating tree");
IntBSTree testTree = new IntBSTree();
System.out.println("Populating Tree with values");
int[] valArr = { 4, 8, 10, 2, 1, 7, 3, 5, 9, 6 };
for (int i : valArr) {
testTree.insert(i);
}
System.out.println("Testing insertion by in-order traversal");
testTree.printInorder();
System.out.println("Testing breadth order traversal");
testTree.printBreadthOrder();
System.out.println("Getting depth of 6");
System.out.println(testTree.getDepth(6));
System.out.println("Getting depth of 14");
System.out.println(testTree.getDepth(14));
}
}
--------------------------------------------------
3. Output: Output is given below
----------------------------------------------
Int BST Tester!
Creating tree
Populating Tree with values
Testing insertion by in-order traversal
1
2
3
4
5
6
7
8
9
10
Testing breadth order traversal
4
2
8
1
3
7
10
5
9
6
Getting depth of 6
4
Getting depth of 14
-1
---------------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.