Question

In: Computer Science

You are given a reference to the root node of a binary search tree, that implements...

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;
}
}

Solutions

Expert Solution

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();
  }
}

Related Solutions

You are given a reference to the root node of a binary search tree, that implements...
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...
1. Draw a binary search tree as a single root node holding a string as the...
1. Draw a binary search tree as a single root node holding a string as the data element. Each string inserted into a node in the tree will be for a character in a game. Then, draw a new tree each time you insert a new node into the tree holding a string Insert 4 nodes total, including the root. This means the new nodes will need to be inserted at the correct child to maintain the BST property.
(+5) Level of a node in a binary tree is distance from root to that node....
(+5) Level of a node in a binary tree is distance from root to that node. For example, level of root is 0 and levels of left and right children of the root are 1. Level      Max number of nodes 1 2 4 8 16 32 64 ..      … n       ?? The maximum number of nodes on level n of a binary tree is : A          2^(n-1)                         B          2^n C          2^(n+1)                       D            2^[(n+1)//2] In the above answers, the operator...
IN JAVA Given a binary search tree, extract min operation finds the node with minimum key...
IN JAVA Given a binary search tree, extract min operation finds the node with minimum key and then takes it out of the tree. The program can be C++/Java or C-style pseudocode. Do not use function call to either Min or delete done in the class. Write this from scratch. (No need to ensure AVL properties, just show it for a generic BST) Node * extract min(Node * x) { }
PYTHON CODING Using the structural node and methods discussed in Binary Search Tree below # Binary...
PYTHON CODING Using the structural node and methods discussed in Binary Search Tree below # Binary Tree Node structure class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None class BSTree(): def __init__(self, rootdata): self.root = Node(rootdata)    def insert(self, data, cur_node): if data < cur_node.data: if cur_node.left == None: cur_node.left = Node(data) else: self.insert(data, cur_node.left)    elif data > cur_node.data: if cur_node.right == None: cur_node.right = Node(data) else:...
/** * This class implements a basic Binary Search Tree that supports insert and get operations....
/** * This class implements a basic Binary Search Tree that supports insert and get operations. In * addition, the implementation supports traversing the tree in pre-, post-, and in-order. Each node * of the tree stores a key, value pair. * * @param <K> The key type for this tree. Instances of this type are used to look up key, value * pairs in the tree. * @param <V> The value type for this tree. An instance of this...
Implement a function to find a node in a binary search tree. Using the following class...
Implement a function to find a node in a binary search tree. Using the following class and function definition. If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr. #include <iostream> class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode *find(int item) { //implement code here return nullptr; } int main() {    root = new...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree worst case and best case time. Learning Outcomes Describe AVL tree structure Trace and implement AVL tree operations Explain and prove AVL tree performance
Beginning with an empty binary search tree, what binary search tree is formed when you insert...
Beginning with an empty binary search tree, what binary search tree is formed when you insert the following values in the given order – consider there alphabetical position for comparison. a. W, T, N, J, E, B, A b. W, T, N, A, B, E, J c. A, B, W, J, N, T, E d. B, T, E, A, N, W, J Alphabetical positions: A-1, B-2, E-5, J-10, N-14,T-20,W-23
Binary Tree Create a binary search tree using the given numbers in the order they’re presented....
Binary Tree Create a binary search tree using the given numbers in the order they’re presented. State if the resulting tree is FULL and/or BALANCED. 37, 20, 18, 56, 40, 42, 12, 5, 6, 77, 20, 54
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT