Trees


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.





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?