Creating a Binary Search Tree without an array

Question

So I have managed to make a BST in Java with using an array but a friend told me he has done it with out using an array. I know roughly how he has done it here is an example(I have left out constructors and getters and setters):

class TreeNode implements Comparable<TreeNode>
{
    private int value;
    private TreeNode leftChild;
    private TreeNode rightChild;
    private TreeNode parent;

As you can see you can just link the left and the right nodes but this got me thing to how the add method would work. So far I have just initialized a new object like this:

public void add(Comparable c)
{
    TreeNode node = new TreeNode(c);
}

But this leaves wondering how can I link to the previous object if I can't access it like it was in an array? and every time I go to link a object I end up adding a new one. I'm kinda confused on how to implement this method, how would you do it?

But you're adding it to an existing node, right? So left, right, and parent have values. — Dave Newton
– Dave Newton, Commented Nov 17, 2015 at 17:57
When you are adding to a TreeNode - where are you adding - left child, right child or parent? In the 'Comparable c' parameter passed in the add() - the corresponding variable should point to 'c'. — TR1
– TR1, Commented Nov 17, 2015 at 17:58
Well I first have to add the root node and then after that I can add to existing nodes. — Definity
– Definity, Commented Nov 17, 2015 at 18:14

EpicPandaForce · Accepted Answer · 2015-11-17 19:51:14Z

I'm pretty sure what you have to do is something akin to this:

class TreeNode<T extends Comparable<T>> {
    private T value;
    private TreeNode<T> left;
    private TreeNode<T> right;
    private TreeNode<T> parent;

    public TreeNode(TreeNode parent, T value) {
        this.parent = parent;
        this.value = value;
    }

    public TreeNode<T> add(T t) {
        if(t.compareTo(value) < 0) {
            if(left == null) {
                left = new TreeNode(this, t);
                return left;
            } else {
                return left.add(t);
            }
        } else {
            if(right == null) {
                right = new TreeNode(this, t);
                return right;
            } else {
                return right.add(t);
            }
        }
    }

    public boolean find(T t) {
        if(t.equals(value)) {
            return true;
        } else {
            if(t.compareTo(value) < 0) {
                if(left == null) {
                    return false;
                } else {
                    return left.find(t);
                }
            } else {
                if(right == null) {
                    return false;
                } else {
                    return right.find(t);
                }
            }
        }
    }
}

class Tree<T extends Comparable<T>> {
    private TreeNode<T> topElement;

    public TreeNode<T> add(T t) {
        if(topElement == null) {
            topElement = new TreeNode(null, t);
            return topElement;
        } else {
            return topElement.add(t);
        }
    }

    public boolean find(T t) {
        if(topElement == null) {
            return false;
        } else {
            return topElement.find(t);
        }
    }
}

Maybe you should use t.compareTo(value) == 0 instead of t.equals(value) here.

Collectives™ on Stack Overflow

Creating a Binary Search Tree without an array

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related