Object oriented design for a Tree

Question

I am implementing a Tree in Java. It must be easy to add a new type of tree e.g. Binary tree and Tertiary tree. Each node can have at least one value. It must be easy to make a new type of node and make a tree of that node.

interface Node<T> {

    T getVal();

    boolean equals(Node<T> node);

    String toString();
}

interface Tree<T extends Node> {
    boolean addNode(T node);

    boolean removeNode(T node);

    String toString();
}

public class BinaryTreeNode<T> implements Node<T> {

    T value;
    BinaryTreeNode<T> firstChild, secondChild;

    BinaryTreeNode(T value) {
        this.value = value;
        firstChild = null;
        secondChild = null;
    }

    public T getVal() {
        return value;
    }

    public boolean equals(Node<T> node) {
        return this.value.equals(node.getVal());
    }

    public String toString() {
        return "" + value;
    }

    boolean setFirstChild(BinaryTreeNode<T> node) {
        firstChild = node;
        return true;
    }

    BinaryTreeNode<T> getFirstChild() {
        return firstChild;
    }

    boolean setSecondChild(BinaryTreeNode<T> node) {
        secondChild = node;
        return true;
    }

    BinaryTreeNode<T> getSecondChild() {
        return secondChild;
    }
}

import java.util.*;

public class BinaryTree<T extends BinaryTreeNode> implements Tree<T> {

BinaryTreeNode root;

    BinaryTree() {
        root = null;
    }

    public boolean addNode(T node) {

        if(root == null) {
            root = node;
        } else {
            addToLast(root, node);
        }

        return true;
    }

    boolean addToLast(BinaryTreeNode root, T node) {

        Deque<BinaryTreeNode> queue = new LinkedList<>();

        queue.addLast(root);
        while(!queue.isEmpty()) {
            BinaryTreeNode cur = queue.pollFirst();

            if(cur.getFirstChild() == null) {
                cur.setFirstChild(node);
                break;
            } else if(cur.getSecondChild() == null) {
                cur.setSecondChild(node);
                break;
            } else {
                queue.addLast(cur.getFirstChild());
                queue.addLast(cur.getSecondChild());
            }
        }

        return true;
    }

    public boolean removeNode(BinaryTreeNode node) {

        throw new UnsupportedOperationException();
    }

    public String toString() {

        Deque<BinaryTreeNode> queue = new LinkedList<>();

        if(root == null) {
            System.out.println("root is null");
            return "";
        }

        StringBuffer ans = new StringBuffer("");
        queue.addLast(root);
        while(!queue.isEmpty()) {
            BinaryTreeNode cur = queue.pollFirst();
            ans.append(" " + cur);

            if(cur.getFirstChild() != null)
                queue.addLast(cur.getFirstChild());

            if(cur.getSecondChild() != null)
                queue.addLast(cur.getSecondChild());

        }

        return ans.toString();
    }

    public static void main(String args[]) {

        BinaryTree<BinaryTreeNode> btree = new BinaryTree<>();

        BinaryTreeNode<Integer> node1 = new BinaryTreeNode<>(1);
        btree.addNode(node1);

        System.out.println(btree);
    }
}

Following this design pattern, I think it is easier to implement different types of binary trees like binary search tree, heap, red-black tree, etc. Also, one can easily add more information to a node while implementing own implementation of tree.

Is this a good design?

I don't understand what effort, if any, you have made to design this code to support other types of trees in the future. — 200_success
– 200_success, Commented Nov 21, 2017 at 1:05
For example, while implementing BinarySearchTree, I will just have to extend BinaryTree and override addNode and removeNode methods. — Varun Raval
– Varun Raval, Commented Nov 21, 2017 at 1:18

Imus · Accepted Answer · 2017-11-21 08:36:14Z

Short answer: no.

But you'll probably need some explanation to believe me.

The whole Node thing you got there should be internal information to the Tree class, not part of the type. Let's look at the following example method to show why it's a bad idea:

private static void addARandomNumber(Tree<Node<Number>> tree) {
    int randomNumber = generateRandomNumber();
    Node<Number> = new ... ???
    tree.addNode(node);
}

What class should we use to create a new Node here?

Had the Node been completely internal to the Tree implementation then the interface would look like this:

interface Tree<T> {
    boolean add(T node);

    boolean remove(T node);

    String toString();
}

And now we can also write the add random number method easily:

private static void addARandomNumber(Tree<Number> tree) {
    int randomNumber = generateRandomNumber();
    tree.add(randomNumber);
}

I also got a feeling that forcing some ordering on T, as required in most search trees, will be rather hard in your current design. But that might just be because I didn't really try it myself yet.

Defining the type of the search tree correctly would probably work, but I expect some type erasure issues with the addNode and removeNode methods.

Stack Exchange Network

Object oriented design for a Tree

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Object oriented design for a Tree

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions