Improving performance with trees

A tree is a hierarchical data structure that consists of parent and child nodes, analogous to that of a physical tree. The topmost node is referred to as the root and there can only be one in a tree data structure. The nodes are the foundational components of this data structure. Each node contains both data and references to child nodes. There are additional terms that you should be familiar with regarding trees. A leaf node has no child. Any node and its descendants can be considered a subtree.

Examples of a tree structure

As shown in the following example, we can implement trees as objects or classes:

class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;
  public TreeNode(int data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

The preceding code snippet defines a TreeNode class that can be...