Tree Implementation using Java

In this post, we will look at a possible Tree Implementation using Java programming language.

Tree is one of the most important non-linear data structure. Tree structure is often seen as a breakthrough in data organization. This is because trees allow us to implement various algorithms much faster as compared to linear data structures like arrays or linked list.

But how do tree data-structures actually work?

So let’s start.

What is a Tree Data Structure?

A tree is a data-structure in which relationship between objects is hierarchical. This means that in a tree some objects are above and some objects are below a given object.

A common place where you might have encountered a tree data-structure is in a family tree or an org chart.

But let’s also look at a more formal definition of a tree.

A tree is an abstract data type where elements are stored hierarchically. Each element in a tree (except the top element) has a unique parent element. Every element also has 0 or more children elements.

The top element in a tree is also known as the root element.

A tree can also be empty. This means it does not have any nodes. This allows us to deal with trees in a recursive manner.

Tree Data Structure Terminologies

Some common terminologies associated with a tree data-structure are as follows:

• Two nodes that are children of the same parent are known as siblings.
• A node is external if it has no children. Such nodes are also known as leaves or leaf nodes.
• A node is internal if it has one or more children.
• An edge of a tree is a pair of nodes (u, v) such that u is the parent of v or vice versa.
• A path in a tree is a sequence of nodes such that any two consecutive nodes in the sequence form an edge.

Step-by-Step Tree Implementation using Java

Now, let’s start with step-by-step Tree Implementation using Java as the programming language.

The Tree Node Definition

Tree is an abstract data type. To define this data type, we use the concept of Position as an abstraction. An element is stored at each position. It also satisfies the parent-child relationship.

Below is the interface for the Position object.

public interface Position<E> {

    /**
     * Returns the element stored at the position
     * @return the stored element
     * @throws IllegalStateException if it is invalid position
     */

    E getElement() throws IllegalStateException;
}

It only has one method getElement() to get the data element stored at the position. Note that we have used Java Generics to define the interface.

The Tree Abstract Data Type

Next step in our Tree Implementation using Java, we have to decide on the functionalities of the Tree Abstract Data Type.

To formalize the Tree ADT, we define the Tree interface. We also use the Position interface.

public interface Tree<E> extends Iterable<E> {
    Position<E> root();
    Position<E> parent(Position<E> p) throws IllegalArgumentException;
    Iterable<Position<E>> children(Position<E> p) throws IllegalArgumentException;
    int numChildren(Position<E> p) throws IllegalArgumentException;
    boolean isRoot(Position<E> p) throws IllegalArgumentException;
    int size();
    boolean isEmpty();
    boolean isInternal(Position<E> p) throws IllegalArgumentException;
    boolean isExternal(Position<E> p) throws IllegalArgumentException;
    Iterator<E> iterator();
    Iterable<Position<E>> positionsPreorder();
    Iterable<Position<E>> positionsPostorder();
}

The above interface has various methods that are required for any type of tree implementation:

• The root() method returns the root node.
• We also have parent() method that takes in a position and returns its parent node.
• The children() method returns the children nodes of a particular position.
• Next, we have numChildren() method that returns the count of the number of children for a node.
• We also have a few boolean methods such as isRoot(), isEmpty(), isInternal() and isExternal().
• Also, we have a size() method that returns the size of the tree i.e. the number of elements in the tree.
• Lastly, we have a few other methods related to tree-traversal which we will discuss in the next post.

The Abstract Tree Base Class

Next, we can implement some methods of the interface as part of the AbstractTree base class.

An abstract class may provide concrete implementations for some of the methods while leaving other abstract methods without implementation. The advantage of this approach is that the final concrete class needs to do less work in terms of implementation.

Below is the AbstractTree class that implements the Tree interface we defined earlier.

public abstract class AbstractTree<E> implements Tree<E> {

    public boolean isRoot(Position<E> p) {
        return p == root();
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean isInternal(Position<E> p) {
        return numChildren(p) > 0;
    }

    public boolean isExternal(Position<E> p) {
        return numChildren(p) == 0;
    }

}

We provide concrete implementation of a few methods from the Tree interface.

Depth of a Tree

Depth of a tree is an important property of a tree data structure. The depth of a position is equal to the number of ancestors of that position other than the position itself.

For example, in the family tree diagram shown above, the depth of 3rd Generation nodes is 2. Also, depth of the root node is 0 because it has no ancestors.

In other words, depth of a position P is one plus the depth of the parent of P. This allows us to calculate the depth of a tree recursively.

Below is the method to calculate the depth recursively in our Tree Implementation using Java. Note that we place the method is the AbstractTree class since it is a common method for all trees.

public int depth(Position<E> p) {
        if (isRoot(p))
            return 0;
        else
            return 1 + depth(parent(p));
}

Note that the above method runs in O(n) worst-case time complexity.

Binary Tree

Binary Tree is a special type of tree. It has a few defining features as below:

• Every node in a Binary Tree has at most two children.
• Each child node has a left child or a right child.
• A left child precedes the right child in the order of children of a node.

Binary Trees have many applications in the form of decision trees and arithmetic expressions. A binary tree can either be:

• An empty tree
• A non-empty tree having a root node r that stores an element and two binary trees that respectively form the left and the right subtrees. One or both of these subtrees can also be empty.

The above properties allow us to define and implement a binary tree in a recursive manner. Let’s understand how we will extend our Tree classes to implement a binary tree.

The Binary Tree Abstract Data Type

Below is the interface for a binary tree. It extends the general tree interface.

public interface BinaryTree<E> extends Tree<E> {

    /**
     * Returns the Position of p's left child (or null if no child exists)
     *
     * @param p
     * @return
     * @throws IllegalArgumentException
     */
    Position<E> left(Position<E> p) throws IllegalArgumentException;

    /**
     * Returns the Position of p's right child (or null if no child exists)
     *
     * @param p
     * @return
     * @throws IllegalArgumentException
     */
    Position<E> right(Position<E> p) throws IllegalArgumentException;

    /**
     * Returns the Position of p's sibling (or null if no sibling exists)
     *
     * @param p
     * @return
     * @throws IllegalArgumentException
     */
    Position<E> sibling(Position<E> p) throws IllegalArgumentException;

}

Basically, there are three additional access methods that are unique to binary trees.

• The left(p) methods returns the position to the left of node p.
• The right(p) returns the position of the right child of p.
• Lastly, the sibling(p) method returns the position of the sibling of p.

Implementing the Abstract Binary Tree Base Class

To increase re-use, we continue use of abstract base classes. To that end, we create an AbstractBinaryTree class that extends from the AbstractTree class. It also implements BinaryTree class and provides concrete implementations of some of the methods.

public abstract class AbstractBinaryTree<E> extends AbstractTree<E> implements BinaryTree<E> {

    @Override
    public Position<E> sibling(Position<E> p) throws IllegalArgumentException {
        Position<E> parent = parent(p);

        if (parent == null) return null;

        if (p == left(parent))
            return right(parent);
        else
            return left(parent);
    }

    @Override
    public int numChildren(Position<E> p) throws IllegalArgumentException {
        int count = 0;

        if (left(p) != null)
            count++;

        if (right(p) != null)
            count++;

        return count;
    }

    @Override
    public Iterable<Position<E>> children(Position<E> p) throws IllegalArgumentException {
        List<Position<E>> snapshot = new ArrayList<>(2);

        if (left(p) != null)
            snapshot.add(left(p));

        if (right(p) != null)
            snapshot.add(right(p));

        return snapshot;
    }

}

We implement the sibling(p) method using the left(p) and right(p) methods. Also, we provide an implementation of the numChildren(p) method. Lastly, we also implement the children(p) method to get the children for a node in a binary tree.

As you can see, all of these methods are reliant on the left(p) and the right(p) method.

The Linked Binary Tree Implementation

We have all the abstract classes and the interfaces required for our tree implementation. However, we cannot actually instantiate any of these classes.

We also have not defined key implementation details about the internal representation of the tree. Also, we have not defined how we will add or update data in the tree.

Therefore, as a next step, we will provide a concrete class for Tree Implementation using Java.

The Nested Node Class

The first step is to implement the Node class by implementing the Position interface we declared earlier.

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

    //Nested node class
    protected static class Node<E> implements Position<E>{

        private E element;
        private Node<E> parent;
        private Node<E> left;
        private Node<E> right;

        public Node(E element, Node<E> parent, Node<E> left, Node<E> right) {
            this.element = element;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        @Override
        public E getElement() {
            return element;
        }

        public Node<E> getParent() {
            return parent;
        }

        public Node<E> getLeft() {
            return left;
        }

        public Node<E> getRight() {
            return right;
        }


        public void setElement(E element) {
            this.element = element;
        }

        public void setParent(Node<E> parent) {
            this.parent = parent;
        }

        public void setLeft(Node<E> left) {
            this.left = left;
        }

        public void setRight(Node<E> right) {
            this.right = right;
        }
    }

The Node class is pretty simple. It has the data element plus references to the parent, left child and right child nodes. We keep the Node class as a nested inner class within the LinkedBinaryTree class. The LinkedBinaryTree class extends AbstractBinaryTree class.

To create a new instance of the node, we declare a factory method as below:

protected Node<E> createNode(E e, Node<E> parent, Node<E> left, Node<E> right){
        return new Node<E>(e, parent, left, right);
}

Also, we declare a couple of instance variables for our tree implementation.

protected Node<E> root = null;
private int size = 0;

One variable stores the root element of the tree. Second is the size of the tree.

Implementing the Tree methods

The other methods we declared as part of the Tree interface are implemented in the LinkedBinaryTree class as below.

    protected Node<E> validate(Position<E> p) throws IllegalArgumentException{
        if(!(p instanceof Node))
            throw new IllegalArgumentException("Not a valid position type");

        Node<E> node = (Node<E>) p;

        if(node.getParent() == node)
            throw new IllegalArgumentException("p is no longer in tree");

        return node;
    }

    public int size(){
        return size;
    }

    public Node<E> root(){
        return root;
    }

    @Override
    public Position<E> parent(Position<E> p) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return node.getParent();
    }

    @Override
    public Position<E> left(Position<E> p) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return node.getLeft();
    }

    @Override
    public Position<E> right(Position<E> p) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return node.getRight();
    }

    public Position<E> addRoot(E e) throws IllegalStateException{
        if(!isEmpty())
            throw new IllegalStateException("Tree is not empty");

        root = createNode(e, null, null, null);
        return root;
    }

    public Position<E> addLeft(Position<E> p, E e) throws IllegalArgumentException{
        Node<E> parent = validate(p);

        if(parent.getLeft() != null)
            throw new IllegalArgumentException("p already has a left child. Use set if you want to update");

        Node<E> child = createNode(e, parent, null, null);
        parent.setLeft(child);
        size++;
        return child;
    }

    public Position<E> addRight(Position<E>p, E e) throws IllegalArgumentException{
        Node<E> parent = validate(p);

        if(parent.getRight() != null)
            throw new IllegalArgumentException("p already has a right child. Use set if you want to update");

        Node<E> child = createNode(e, parent, null, null);
        parent.setRight(child);
        size++;
        return child;
    }

    public E set(Position<E> p, E e) throws IllegalArgumentException{
        Node<E> node = validate(p);
        E temp = node.getElement();
        node.setElement(e);
        return temp;
    }

    public void attach(Position<E> p, LinkedBinaryTree<E> t1, LinkedBinaryTree<E> t2) throws IllegalArgumentException{
        Node<E> node = validate(p);

        if(isInternal(p)) throw new IllegalArgumentException("p must be a leaf");

        size += t1.size() + t2.size();

        if(!t1.isEmpty()){
            t1.root.setParent(node);
            node.setLeft(t1.root);
            t1.root=null;
            t1.size=0;
        }

        if(!t2.isEmpty()){
            t2.root.setParent(node);
            node.setRight(t2.root);
            t2.root = null;
            t2.size=0;
        }
    }

Let’s understand these methods one-by-one.

• validate(p) method takes a position and validates whether the position objects belongs to the Node class. It returns a node object.
• size() returns the current size of the tree. In other words, it returns the number of elements in the tree. Since we keep this variable always updated, the call to size() methods works in O(1) time complexity.
• root() methods returns the root node of the tree. Since we always keep track of the root node, this also runs in O(1) time complexity.
• parent(p) returns the parent of a given position using the Node class methods.
• left(p) and right(p) return the left child and right child of a given position.
• addRoot(p) method creates the root node for the tree. Basically, this method is the first to be called when creating a new tree.
• addLeft(p, e) method takes in the position p and the data element e to be inserted. The data element is then inserted as left child of the given position. Note that this method also run in O(1) time complexity. We also increment the size variable to keep it in sync.
• addRight(p, e) does similar work to addLeft(p) but for the right child.
• attach(p, t1, t2) inserts tree t1 and tree t2 as left and right child of position p. This method also works in O(1) time complexity.

Conclusion

With this we have successfully completed our Tree Implementation using Java.

Basically, we looked at the various abstract classes and interfaces required for our Tree. Then, we went deeper into a special type of tree known as Binary Tree. And we implemented the Binary Tree using a linked node approach.

The code till for this Tree Implementation using Java is available on Github.

For the next post, we will be looking at various Tree Traversal algorithms and their implementation in Java.

If you have any queries, do sound off in the comments section below.