Tree Data Structure with Java

The tree data structure is a type of graph. A tree has a root node (top node) that will have a relationship with its child nodes. The path that connects the root node to the child nodes is called a branch. The leaf node is the node that doesn’t have any children and is not the root node.

In algorithms, you will see a lot of the nomenclature height. Height in trees is the number of nodes from the highest branch to the root node. Another keyword is the depth of a tree which means the count of nodes from a specific node to the root node.

To make those nomenclatures clear, let’s see them in a diagram:

A real-world example is the hierarchy of a company. For example:

To follow and run your own tests from the following code examples, you can download the code here!

Let’s see a simple way to represent this data in Java code:

import java.util.LinkedList;
import java.util.List;

public class TreeNode {

  private String value;
  private List<TreeNode> childNodes;

  public TreeNode(String value) {
    this.value = value;
    this.childNodes = new LinkedList<>();
  }

  public void addChild(TreeNode childNode) {
    this.childNodes.add(childNode);
  }

  public void showTreeNodes() {
    BreathFirstSearchPrintTreeNodes.printNodes(this);
  }

  public String getValue() {
    return value;
  }

  public List<TreeNode> getChildNodes() {
    return childNodes;
  }
}

Notice that the code above is very similar to the graph data structure. We are also using the Breadth-first search algorithm to show the data from the tree. For now, don’t worry about it, just keep in mind that this is a famous algorithm that will visit and print each node. Now let’s populate the data from the company hierarchy in the Tree data structure:

public class CompanyHierarchyTree {

  public static void main(String[] args) {
    TreeNode rootTreeNode = new TreeNode("CEO");
    TreeNode vpNode = new TreeNode("Vice President");
    TreeNode managerNode = new TreeNode("Manager");
    TreeNode dev1Node = new TreeNode("Developer 1");
    TreeNode dev2Node = new TreeNode("Developer 2");
    TreeNode dev3Node = new TreeNode("Developer 3");
    rootTreeNode.addChild(vpNode);
    vpNode.addChild(managerNode);
    managerNode.addChild(dev1Node);
    managerNode.addChild(dev2Node);
    managerNode.addChild(dev3Node);

    rootTreeNode.showTreeNodes();
  }

}

Output:
Visited nodes: CEO | Vice President | Manager | Developer 1 | Developer 2 | Developer 3 |

Another example is the way file system on a computer. There is a hierarchy of compartments within the computer to organize files. For example, there is the root computer compartment and then users, the Desktop, and finally your file.  This is a classic example of a tree data structure.

A tree can’t have cycles and each node can’t have more than one parent.

Binary Tree

A binary tree is a tree that has up to 2 child nodes. Let’s see how that works in a diagram:

Notice that the diagram above is a binary tree because the nodes have up to 2 children at max. Even though node 3 has only one child that still makes the above diagram a binary tree.

Ternary Tree

A ternary tree is similar to the binary tree but instead of having up to 2 child nodes, it has up to 3 child nodes. Let’s see how this is represented in a diagram:

Notice in the diagram above that node 1 and node 2 has 3 child nodes. Even though node 4 has only one child node this also doesn’t matter, it’s still a ternary tree since the max number of child nodes is 3.

K-ary tree

The “K” represents the max number of child nodes a tree can have. For example, we can represent a binary tree as a 2-ary tree because both mean that the tree can have up to 2 child nodes. Similarly, a 3-ary tree is the same as a ternary tree

Perfect Binary Tree

A perfect binary tree has the same depth for every child node to the leaf nodes. Let’s see how to represent it in a diagram:

Complete Binary Tree

A complete binary tree contains its nodes complete for the leftmost nodes. Also, the interior nodes have to have two child nodes. Only the leaf nodes that are not the leftmost are allowed to not have child nodes.

Remember that if the binary tree is complete only for the rightmost nodes, that wouldn’t be considered a complete binary tree.

Full Binary Tree

When a tree has either two or zero child nodes, it’s considered a full binary tree. To illustrate a full binary tree, take a look at the following diagram:

Balanced Binary Tree

A balanced tree can’t have its subtrees heights with more than 1 level of difference between the left and right subtrees. Let’s see an example to understand it more clearly:

Notice in the diagram above that the total height of this tree is 3. The height of the left nodes 4 and 5 is 3. The height of node 3 is 2. Therefore, the difference between the node subtrees is 1, and for this reason, is a balanced tree.

The following diagram is an example of a non-balanced binary tree. That’s because the height from the left subtrees is higher than 1 compared to the right subtrees:

Note that in the diagram above node 6 has a height of 4. Node 3 which is on the right has a height of 2. Therefore, the difference in the height of the nodes is higher than 1 and for this reason, the tree above is not a balanced tree.