Question

Instructions

Create a class BettterTree that extends OurTree, to facilitate the following.

Update: if extending the class is too much, you can modify class OurTree.

In our discussions about OurTree, we focused on nodes and their left and right children. For each node in the tree, is there another node of interest in addition to its children? If yes, how would you extend OurTree for that? How will the behavior of addNode method change?

OurTree Code:

public class OurTree {
	/**
	* Class OurTree has a special node called root, marking the
	* beginning of a tree.
	*/
	Node root;
	/**
	* Field to capture the total number of nodes in the tree.
	*/
	int size = 0;
	/**
	* Class Node is the building block for class Tree. It's an object
	* that comprises the data we wish to store (here a String called
	* content), and pointers to the left and right child nodes.
	*
	* +---------------+
	* | this node |
	* +---------------+
	* | content |
	* +-------+-------+
	* | left | right |
	* +-------+-------+
	* / \
	* / \
	* left right
	* child child
	*/
	class Node {
	String content;
	Node left;
	Node right;
	/** Basic constructor: add content, leave pointers null */
	Node(String s) {
	content = s;
	left = null;
	right = null;
	} // constructor Node
	} // class Node
	/**
	* Method to insert a note to tree, using recursion. The method returns a Node
	* object, and it has to be called from a node assignment statement, indicating
	* the starting point of insertion. Since all insertions begin from root, the
	* standard invocation of this recursive method must be:
	* root = addRecursively(root, String s)
	*
	* @param current Node where the insertion begins from (usually, the root)
	* @param s Data to insert as a node in the tree.
	* @return The top node of the tree, in a successful insertion.
	*/
	private Node recursiveInsertion(Node current, String s) {
	/*
	If the current node is empty, "wrap" the data into a node object
	and place it here.
	*/
	if ( current == null ) {
	current = new Node(s);
	size++;
	return current;
	}
	/*
	If the starting node for insertion is not empty, we need to look
	if the new data should be placed to the left or the right of the
	node. Since we are dealing with Strings, we use the compareTo()
	method to determine the relation between the string we are trying to
	insert and the value held by the current node.
	*/
	if (s.compareTo(current.content) < 0) {
	current.left = recursiveInsertion(current.left, s);
	} else if (s.compareTo(current.content) > 0) {
	current.right = recursiveInsertion(current.right, s);
	}
	/*
	If we make it this far, it's because the new data (String s) we are
	trying to insert in the tree, already exists and we just found it
	as the content of the current node.
	*/
	return current;
	} // method recursiveInsertion
	/**
	* Wrapper method for the recursive insertion. It starts from the root
	* node and lets the recursion take charge until it finds an place for
	* the new node containing s. The method, when it executes correctly
	* (and it always does) returns the root node of the tree. This may seem
	* risky, allowing a method to potentially change the root node. The
	* method, however, will always return the root node of the tree.
	*
	* @param s Data we wish to insert in the tree.
	*/
	public void addNode(String s) {
	root = recursiveInsertion(root,s);
	} // method add
	/** A quick accessor for the contents of the root node */
	public String getRootContent() { return root.content; }
	/** A quick accessor for the size of the tree */
	public int getSize() { return size; }
	public void displayInOrder(Node node) {
	if (node==null) {
	return;
	}
	displayInOrder(node.left);
	System.out.println(node.content);
	displayInOrder(node.right);
	}
	public void displayInOrder() { displayInOrder(root);}
	public static void main(String[] args) {
	OurTree sycamore = new OurTree();
	sycamore.addNode("m");
	sycamore.addNode("k");
	sycamore.addNode("t");
	sycamore.addNode("r");
	sycamore.addNode("b");
	sycamore.addNode("f");
	sycamore.addNode("z");
	sycamore.addNode("g");
	//System.out.println(sycamore.getRootContent());
	// \System.out.println(sycamore.getSize());
	sycamore.displayInOrder();
	} // method main
	} // class OurTree

Code should start with:

public class BetterTree extends OurTree {
	}

Answer 1

I have changed the structure of tree node in BetterTree. Now, tree nodes of Better tree are having reference to parent nodes as well. So the tree structure looks like this:

Smith Baker Wilson V Able Jones

Updated java code with BetterTree class:

public class OurTree {
/**
* Class OurTree has a special node called root, marking the
* beginning of a tree.
*/
Node root;
/**
* Field to capture the total number of nodes in the tree.
*/
int size = 0;
/**
* Class Node is the building block for class Tree. It's an object
* that comprises the data we wish to store (here a String called
* content), and pointers to the left and right child nodes.
*
* +---------------+
* | this node |
* +---------------+
* | content |
* +-------+-------+
* | left | right |
* +-------+-------+
* / \
* / \
* left right
* child child
*/
class Node {
String content;
Node left;
Node right;
/** Basic constructor: add content, leave pointers null */
Node(String s) {
content = s;
left = null;
right = null;
} // constructor Node
} // class Node
/**
* Method to insert a note to tree, using recursion. The method returns a Node
* object, and it has to be called from a node assignment statement, indicating
* the starting point of insertion. Since all insertions begin from root, the
* standard invocation of this recursive method must be:
* root = addRecursively(root, String s)
*
* @param current Node where the insertion begins from (usually, the root)
* @param s Data to insert as a node in the tree.
* @return The top node of the tree, in a successful insertion.
*/
private Node recursiveInsertion(Node current, String s) {
/*
If the current node is empty, "wrap" the data into a node object
and place it here.
*/
if ( current == null ) {
current = new Node(s);
size++;
return current;
}
/*
If the starting node for insertion is not empty, we need to look
if the new data should be placed to the left or the right of the
node. Since we are dealing with Strings, we use the compareTo()
method to determine the relation between the string we are trying to
insert and the value held by the current node.
*/
if (s.compareTo(current.content) < 0) {
current.left = recursiveInsertion(current.left, s);
} else if (s.compareTo(current.content) > 0) {
current.right = recursiveInsertion(current.right, s);
}
/*
If we make it this far, it's because the new data (String s) we are
trying to insert in the tree, already exists and we just found it
as the content of the current node.
*/
return current;
} // method recursiveInsertion
/**
* Wrapper method for the recursive insertion. It starts from the root
* node and lets the recursion take charge until it finds an place for
* the new node containing s. The method, when it executes correctly
* (and it always does) returns the root node of the tree. This may seem
* risky, allowing a method to potentially change the root node. The
* method, however, will always return the root node of the tree.
*
* @param s Data we wish to insert in the tree.
*/
public void addNode(String s) {
root = recursiveInsertion(root,s);
} // method add
/** A quick accessor for the contents of the root node */
public String getRootContent() { return root.content; }
/** A quick accessor for the size of the tree */
public int getSize() { return size; }
public void displayInOrder(Node node) {
if (node==null) {
return;
}
displayInOrder(node.left);
System.out.println(node.content);
displayInOrder(node.right);
}
public void displayInOrder() { displayInOrder(root);}
public static void main(String[] args) {
BetterTree sycamore = new BetterTree();
sycamore.addNode("m");
sycamore.addNode("k");
sycamore.addNode("t");
sycamore.addNode("r");
sycamore.addNode("b");
sycamore.addNode("f");
sycamore.addNode("z");
sycamore.addNode("g");
//System.out.println(sycamore.getRootContent());
// \System.out.println(sycamore.getSize());
sycamore.displayInOrder(sycamore.root);
} // method main
} // class OurTree

class BetterTree extends OurTree{
NewNode root;
class NewNode extends Node{
public NewNode left = null;
public NewNode right = null;
public NewNode parent;
public NewNode(String s){
super(s);
content = s;
left = null;
right = null;
parent = null;
}
}
//override the recursive method
private NewNode recursiveInsertion(NewNode current, String s) {
/*
If the current node is empty, "wrap" the data into a node object
and place it here.
*/
if ( current == null ) {
current = new NewNode(s);
size++;
return current;
}
/*
If the starting node for insertion is not empty, we need to look
if the new data should be placed to the left or the right of the
node. Since we are dealing with Strings, we use the compareTo()
method to determine the relation between the string we are trying to
insert and the value held by the current node.
*/
if (s.compareTo(current.content) < 0) {
if(current.left==null){
current.left = new NewNode(s);
current.left.parent = current;
return current;
}else current.left = this.recursiveInsertion(current.left, s);
} else if (s.compareTo(current.content) > 0) {
if(current.right==null){
current.right = new NewNode(s);
current.right.parent = current;
return current;
}else current.right = this.recursiveInsertion(current.right, s);
}
/*
If we make it this far, it's because the new data (String s) we are
trying to insert in the tree, already exists and we just found it
as the content of the current node.
*/
return current;
}
public void addNode(String s) {
root = this.recursiveInsertion(root,s);
} // method add
public void displayInOrder(NewNode node) {
if (node==null) {
return;
}
displayInOrder(node.left);
System.out.println(node.content);
displayInOrder(node.right);
}
public int getSize(){
return this.size;
}
}