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.

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?