1
\$\begingroup\$

I have a binary tree below and it seems to make sense to overload the insert() method. If insert() is called without a Node specified, it will just work with head, otherwise if it receives a Node, it will do the insert in the subtree starting with that Node. This second variant is then called recursively, see below.

The repetition that happens in the code below seems wrong to me (not DRY). Is there a better way to do this or is this a limitation in Java?

public class probBinaryTree {
    public Node head;

    public probBinaryTree() {
        this.head = null;
    }   

    private class Node {
        int data;
        Node left;
        Node right;
        int size;

        public Node(int d) {
            this.data = d;
            this.left = null;
            this.right = null;
            this.size = 1;
        }
    }

    public Node insert(int d) {
        if (head == null) {
            head = new Node(d);
            return head;
        }
        head.size++;
        if (head.left == null) return insert(head.left, d);
        if (head.right == null) return insert(head.right, d);
        if (head.left.size <= head.right.size) return insert(head.left, d);
        if (head.left.size > head.right.size) return insert(head.right, d);
        return null;
    }

    private Node insert(Node n, int d) {
        if (n == null) {
            n = new Node(d);
            return n;
        }
        n.size++;
        if (n.left == null) return insert(n.left, d);
        if (n.right == null) return insert(n.right, d);
        if (n.left.size <= n.right.size) return insert(n.left, d);
        if (n.left.size > n.right.size) return insert(n.right, d);
        return null;
    }
}
\$\endgroup\$
1
\$\begingroup\$

Just have one insert method call the other. In your code, that would look like:

public final class BinaryTree {

    public Node head;

    public BinaryTree() {
        this.head = null;
    }

    private class Node {
        private final int data;
        private final Node left;
        private final Node right;
        private int size;

        public Node(final int d) {
            this.data = d;
            this.left = null;
            this.right = null;
            this.size = 1;
        }
    }

    public Node insert(final int d) {
        if (this.head == null) {
            this.head = new Node(d);
            return this.head;
        }

        return this.insert(this.head, d);
    }

    private Node insert(final Node n, final int d) {
        if (n == null) {
            return new Node(d);
        }

        n.size++;
        if (n.left == null) {
            return this.insert(n.left, d);
        }
        if (n.right == null) {
            return this.insert(n.right, d);
        }
        if (n.left.size <= n.right.size) {
            return this.insert(n.left, d);
        }
        if (n.left.size > n.right.size) {
            return this.insert(n.right, d);
        }
        return null;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.