Trees

There are two ways to describe the shape of a tree. Trees can be wide, meaning that each node has many children. And trees can be deep, meaning that there are many parent-child connections with few siblings per node. Trees can be both wide and deep at the same time.

In a binary search tree, parent nodes can have a maximum of two children. These children are called the “left child” and the “right child”. A binary search tree requires that the values stored by the left child are less than the value of the parent, and the values stored by the right child are greater than that of the parent.

Trees in computer science are often talked about similarly to family trees. A tree node that references one or more other nodes is called a “parent”.

A tree node can be a “parent” and a “child” simultaneously, because they are not exclusive. For instance, a node ‘b’ can be the child of node ‘a’, while being the parent to nodes ‘d’ and ‘e’. However, a child can only have one parent, while a parent can have multiple children.

Trees are a data structure composed of nodes used for storing hierarchical data.

Each tree node typically stores a value and references to its child nodes.

A tree node contains a value, and can also include references to one or more additional tree nodes which are known as “children”.

To implement a general Tree data structure, we can create a TreeNode class in Java with the following behavior:

• constructor with data and children instance variables
• .addChild() method to add a child to the TreeNode
• .removeChild() method to remove a child from the descendants of the TreeNode

and a Tree class with the following behavior:

• .print() method to print the tree
• .depthFirstTraversal() method that prints the depth-first traversal of the tree
• .breadthFirstTraversal() method that prints the breadth-first traversal of the tree

A TreeNode has two .addChild() methods.

    public void addChild(TreeNode child) {
        this.children.add(child);
    }

    public void addChild(Object childData) {
        TreeNode child = new TreeNode(childData);
        this.children.add(child);
    }

A TreeNode should have .removeChild() methods that take either a specific TreeNode instance or a piece of data to search for. The implementation looks like this:

public void removeChild(TreeNode childToRemove) {
        if (this.children.isEmpty()) {
            return;
        } else if (this.children.contains(childToRemove)) {
            this.children.remove(childToRemove);
            return;
        } else {
            for (TreeNode child : this.children) {
                child.removeChild(childToRemove);
            }
        }
}

    public void removeChild(Object data) {
        if (this.children.isEmpty()) {
            return;
        }
        for (TreeNode child : this.children) {
            if (child.data == data) {
                removeChild(child);
                return;
            }
        }
        for (TreeNode child : this.children) {
            child.removeChild(data);
        }
    }

The .depthFirstTraversal() method in the Tree class should print the depth-first traversal of the tree using recursion. It takes nothing and returns nothing.

The code looks like this:

public void depthFirstTraversal(TreeNode current) {
   System.out.print(current.data + " ");
   for (TreeNode child : current.children) {
     depthFirstTraversal(child);
   }
}

The .breadthFirstTraversal() method in the Tree class should print the breadth first traversal of the tree. It takes nothing and returns nothing. To implement this, we use a Queue data structure to maintain the order of children added.

The code looks like this:

  public void breadthFirstTraversal() {
    TreeNode current = this.root;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(current);
    while (!queue.isEmpty()) {
      current = queue.poll();
      System.out.print(current.data + " ");
      queue.addAll(current.children);
    }
  }