Trees are an important data structure. They can store and retrieve information quickly. Arrays are not as efficient as binary trees at retrieving information because on average they take O(n^2) time and at best O(nlog(n)). Binary trees are more efficient because their average retrieval time is O(log(n)).

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 sub-tree and the right sub-tree). 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 n-squared 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:

  1. Create a new BST
  2. Add a node
  3. Delete a node
  4. Search for an integer value
  5. Report the largest integer value
  6. Report the smallest integer value
  7. Delete a BST
  8. 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
I have completed the project(s) for this lesson and have demonstrated them to my instructor.

Review Quiz on Trees
  1. 1 point

    Does this picture represent a binary tree?
  2. 1 point

    Does this picture represent a binary tree?
  3. 1 point

    Does this picture represent a binary tree?
  4. 1 point

    Does this picture represent a binary tree?
  5. 1 point

    What is the relationship between nodes 8 and 3?