Trees
Binary trees have many different parts and to truly understand them, you will need to know the following definitions:
Nodes  The different parts of a binary tree that carry additional information. This may include its name.
Edges  Edges connects 2 nodes to show a relationship. Nodes, besides the root, may only have one incoming edge but can have as many as 2 going out.
Root  The only node without any incoming edges. It is the start of the entire tree.
Path  An ordered list of nodes connected through incoming and outgoing edges.
Parent  A node is the parent of all of its outgoing edges.
Children  A set of nodes that have incoming edges from the same node are the children of that node. Every child has only one parent but every parent can have up to two children.
Siblings  Nodes that share the same parent node.
Subtree  Parts of a binary tree that contain nodes and edges. Comprised of a parent and all its descendants.
External Node (Leaf Node)  A node that does not have any children.
Internal Node  A node with at least one child.
Level  The level of a node is 1 + (number of edges to the root from that node).
Height  The number of edges from the node to the farthest leaf node only going down the binary tree. (The height of the tree is equal to the height of the root node)
Depth  The number of edges from the node to the root node of the tree.
In a tree an edge is never shared among two or more nodes. For example one edge cannot branch out to connect to two different nodes. A circular path of nodes which contains a loop is also not considered a tree as a tree cannot have a child node pointing to another node below its level. The higher up you go in a tree, the lower the level of the node.
Also, even though one solo node is considered a tree, a node cannot have an edge pointing to itself, this would mean that the node is its own child
Caution: In a binary tree all the nodes are connected without any separation. If there are two trees in one picture and they are not connected, the picture does not represent a tree. Even if the trees have no mistake, they still cannot be counted as different trees unless it has been said in the description. Always assume that the image is of one tree only.
The following is not a tree because all the nodes of a tree have to be connected to each other:Video Presentation on Trees
Here is an example of how to create a binary tree. There are many methods but this one is the easiest to understand. It uses three classes, a node class, a tree class, and a tester class.
Public class Node{
//Class for the nodes of the tree
int key;
//Key is the value of the node, this can be anything you want like a string or boolean
//The two children
Node left;
Node right;
//Creates a leaf node, children are specified to null but can later be changed to hold values
public Node(int key){
this.key = key;
left = right = null;
}
//toString() method to help print values later if needed
public String toString(){
return “The value of this node is” + key;
}
}
Public class BinaryTree{
//Holds all the nodes to form the binary tree
//Create the start of the tree
Node root;
//Default constructor
public BinaryTree(){
root = null;
}
//Constructor for node that has already been created
public BinaryTree(Node root){
this.root = root;
}
}
Public class Tester{
//Test and create the binary tree
public static void main(String [] args){
//Define all the nodes (Ex. Using picture from above as binary tree)
Node n2 = new Node(2);
Node n7 = new Node(7);
Node n5 = new Node(5);
Node na2 = new Node(2);
Node n6 = new Node(6);
Node n9 = new Node(9);
Node n5 = new Node(5);
Node n11 = new Node(11);
Node n4 = new Node(4);
//Define the tree
BinaryTree tree = new BinaryTree(n2)
//n2 is the root
//Define all the children
n2.left = n7;
n2.right = n5;
n7.left = na2;
n7.right = n6;
n5.right = n9;
n6.left = n5;
n6.right = n11;
n9 .left = n4;
}
}
The code above only creates a binary tree but does not do anything. To iterate through a binary tree we will have to traverse it. There are three ways to do this, preorder, inorder, and postorder. Preorder, the easiest, is shown recursively below.
public void preorder(Node root) {
if(root != null) {
//Will print the value of the current node
System.out.print(root.key);
preorder(root.left);
preorder(root.right);
}
}
This code is only sample code and if you use it you will notice that it prints values in the same line. You can always modify it to give it more of a tree shape.
Binary Search Tree (BST) Programming Assignment
We will focus our tree efforts in this class on binary trees. These are data structures for which each node has at most two children (the left subtree and the right subtree). Binary trees are powerful because they can be used to save and retrieve information quickly.
We learned earlier this year that if we simply choose to store information in an array, sorting that information later or trying to locate an individual element within the array can be time consuming  from nsquared time to at best n* log(n).
The use of trees can reduce the processing times significantly. Of course, this becomes important once the data grows substantially. Restricting the tree to be a binary tree greatly simplifies coding and implementation. The resulting structure is also easier for the user to understand.
When we use a binary tree to save and retrieve information, the term Binary Search Tree (BST) is used.
Your grade on this lesson will be driven of your ability to create, document, and demo the following program.
You must create a BST program that visually displays a Binary Search Tree that holds an integer as its data. The user must be presented with the following menu for the tree:
Binary Search Tree Menu:
 Create a new BST
 Add a node
 Delete a node
 Search for an integer value
 Report the largest integer value
 Report the smallest integer value
 Delete a BST
 Exit
Your program should continuously update the BST after each selection and display the newly updated tree. You can use any graphical package you wish to display the information for the tree.
It is ok with your instructor if you work with your peers to select the same graphing scheme and share it (even share the same graphing code) as this is not a major part of the assignment. The code for the tree, and its operations, of course, cannot be shared.
Example Tree Output
So after creating the BST and putting a bunch of stuff in it, the tree display may look like this:
If you find it difficult to draw the circles around each integer node value, you may omit the circles. But some sort of directional arrowheads must be present to indicate parents versus children nodes of the tree.
YOUR TREE MUST BE DISPLAYED TOP TO BOTTOM AND NOT LEFT TO RIGHT. (Talk to your instructor if this is in any way unclear).

1 point
Does this picture represent a binary tree? 
1 point
Does this picture represent a binary tree? 
1 point
Does this picture represent a binary tree? 
1 point
Does this picture represent a binary tree? 
1 point
What is the relationship between nodes 8 and 3?