In: Computer Science
You are given a reference to the root node of a binary search tree, that implements a dictionary data structure. Please print all the elements in depths 500 through 510, all in sorted order. A node in a binary search tree is at depth x, if it takes x hops to get from the root. So the root is at depth 0, the children of the root are at depth 1, and so on. The class TreeNode defines a single node in the binary search tree, and the file MyTree.class is a pre-compiled Java code that defines a binary search tree. The file DepthPrint.java creates an instance of MyTree, and gets the root node of the tree. Please write code that will print elements in depths 500 through 510 in sorted order. Please feel free to add new methods, instance fields and classes that will help your implementation. Your output should match the file depthprint.out.
DepthPrint.java:
public class DepthPrint {
public static void main(String [] args) {
// Create an instance of MyTree.
MyTree T = new MyTree();
// Get the root node of my tree.
TreeNode root = T.getRoot();
// TODO: Code for printing the tree
from depth 500 through 510 in sorted order.
// Feel free to define recursive
methods to traverse the tree and print.
// Please print each key separated
by spaces.
// Printing a new line in the
end.
System.out.println();
}
}
TreeNode.java:
public class TreeNode
{
public int key;
public TreeNode left;
public TreeNode right;
public TreeNode(int _key)
{
key = _key;
left = null;
right = null;
}
}
MyTree.java:
public class MyTree
{
private TreeNode root;
private TreeNode insert(final TreeNode treeNode, final int
n)
{
if (treeNode == null)
{
return new TreeNode(n);
}
if (n <= treeNode.key)
{
treeNode.left = this.insert(treeNode.left, n);
}
else
{
treeNode.right = this.insert(treeNode.right, n);
}
return treeNode;
}
public MyTree()
{
this.root = null;
System.out.println("Loading my Tree.");
for (int i = 0; i < 10000; ++i)
{
if ((i & 0x1) == 0x1)
{
this.root = this.insert(this.root, -i);
}
else
{
this.root = this.insert(this.root, i);
}
}
System.out.println("My Tree is loaded.");
}
public TreeNode getRoot()
{
return this.root;
}
}
PLEASE GIVE IT A THUMBS UP, I SERIOUSLY NEED ONE, IF YOU NEED ANY MODIFICATION THEN LET ME KNOW, I WILL DO IT FOR YOU
class TreeNode {
public int key;
public TreeNode left;
public TreeNode right;
public TreeNode(int _key) {
key = _key;
left = null;
right = null;
}
}
class MyTree {
private TreeNode root;
private TreeNode insert(final TreeNode treeNode, final int n) {
if (treeNode == null) {
return new TreeNode(n);
}
if (n <= treeNode.key) {
treeNode.left = this.insert(treeNode.left, n);
} else {
treeNode.right = this.insert(treeNode.right, n);
}
return treeNode;
}
public MyTree() {
this.root = null;
System.out.println("Loading my Tree.");
for (int i = 0; i < 100; ++i) {
if ((i & 0x1) == 0x1) {
this.root = this.insert(this.root, -i);
} else {
this.root = this.insert(this.root, i);
}
}
System.out.println("My Tree is loaded.");
}
public TreeNode getRoot() {
return this.root;
}
}
class DepthPrint {
// we are using inorder traversal technique as we have to print in sorted order , and printing only those values whose depth is inside the desired range.
public static void traverse_tree(
TreeNode node,
int depth,
int min_depth,
int max_depth
) {
if (node == null) {
return;
}
traverse_tree(node.left, depth + 1, min_depth, max_depth);
if (depth >= min_depth && depth <= max_depth) {
System.out.print(node.key + " ");
}
traverse_tree(node.right, depth + 1, min_depth, max_depth);
}
public static void main(String[] args) {
MyTree T = new MyTree();
TreeNode root = T.getRoot();
int min_depth = 0;
int max_depth = 10;
System.out.print(
"Printing Tree structure in sorted manner from depth " +
min_depth +
" to " +
max_depth +
" : "
);
traverse_tree(root, 0, min_depth, max_depth);
System.out.println();
}
}