Homework answers / question archive / 1) (40 points) Complete the implementation of maxDepth() method

1) (40 points) Complete the implementation of maxDepth() method

Computer Science

Share With

---

1) (40 points) Complete the implementation of maxDepth() method. Write a recursive method so that it calculates and returns the maximum depth of the tree. You may use helper functions, if necessary.

 

2. (60 points) In the main() function, try inserting numbers from 1 to 9 with various different orders, so that the depth of the tree is minimum.

For example, insert 4 first, then 2, then 8, and so on. Or make another trial with inserting numbers from 9 to 1 in decreasing order.

After each of your trial, print out maxDepth() to see whether the tree is balanced well or not.

 

First, manually calculate what smallest value of depth is possible with nine elements.

While writing code to insert elements, you may try inserting values one by one with desired order or within some loops or within some functions.

Do not modify inside of insert() method. We do not need a new insert() method that can automatically balance the tree, we need to use the existing insert() method in TinyBST, but we need to intelligently call insert() method with such an order that the resulting binary search tree is balanced. (Hence the depth is minimum.)

 

3. (50 bonus points) Is it possible to build a generic code to insert n consecutive numbers into the TinyBST, so that the resulting tree is guaranteed to have the minimum possible depth?

If so, please write the code that asks for a number n and inserts n consecutive integers from 1 to n into the Binary Search Tree with such an order that the depth of the tree is minimal. 

 

Do not modify inside of insert() method.

Please run a few different experiments to insert number from 1 to 3, another experiment to insert numbers from 1 to 7, from 1 to 15, from 1 to 31, and from 1 to 63 to see how well your algorithm is performing.

 

Use the attached TinyBST.java file.

public class TinyBST {
  protected TreeNode<Integer> root;

  /** Returns true if the element is in the tree */
  public boolean search(Integer e) {
    TreeNode<Integer> current = root; // Start from the root

    while (current != null) {
      if (e < current.element) {
        current = current.left;
      }
      else if (e > current.element) {
        current = current.right;
      }
      else // element matches current.element
        return true; // Element is found
    }

    return false;
  }

  /** Insert element e into the binary tree
    * Return true if the element is inserted successfully */
  public boolean insert(Integer e) {
    if (root == null)
      root = createNewNode(e); // Create a new root
    else {
      // Locate the parent node
      TreeNode<Integer> parent = null;
      TreeNode<Integer> current = root;
      while (current != null)
        if (e < current.element) {
          parent = current;
          current = current.left;
        }
        else if (e > current.element) {
          parent = current;
          current = current.right;
        }
        else
          return false; // Duplicate node not inserted

      // Create the new node and attach it to the parent node
      if (e < parent.element)
        parent.left = createNewNode(e);
      else
        parent.right = createNewNode(e);
    }

    return true; // Element inserted successfully
  }

  protected TreeNode<Integer> createNewNode(Integer e) {
    return new TreeNode<>(e);
  }

  /** This inner class is static, because it does not access 
      any instance members defined in its outer class */
  public static class TreeNode<E> {
    protected E element;
    protected TreeNode<E> left;
    protected TreeNode<E> right;

    public TreeNode(E e) {
      element = e;
    }
  }

  /** Remove all elements from the tree */
  public void clear() {
    root = null;
  }

  /** calculate maximum depth of the tree */
  public int maxDepth() {
	// complete this function. use helper methods if necessary.
  }
  
  public static void main(String[] args) {
	  
		var test = new TinyBST();
		
		for (int i=1; i<=9; i++)
			test.insert(i);
		
		System.out.println(test.maxDepth());
		
		test.clear();
		
		// try with different orders of insert()
		// . . .
		
	}
}