How to add to a Binary Search Tree without using a Node class

Question

For class I need to create my own binary search tree implementation including a search,add, remove and toString method but I cannot try those methods without add first. I am not allowed to write or use a node class. Each node of my tree is supposed to be an instance of the BinarySearchTree class. I cannot figure out how to traverse the tree without the typical nodes. Here's my first portion of code:

public class BinarySearchTree<E extends Comparable<E>> implements BinarySearchTreeInterface<E> {
    E value;
    BinarySearchTree<E> parent;
    BinarySearchTree<E> left;
    BinarySearchTree<E> right;
    static String draw;

    public BinarySearchTree() {
        value = null;
        parent = null;
        left = null;
        right = null;
    }

    @Override
    public void add(E item) {
        if (isRoot() && value == null) {
            value = item;

        } else if (value.compareTo(item) > 0) {
            if (right != null) {
                add(right.value);
            } else {
                BinarySearchTree<E> newNode = new BinarySearchTree<E>();
                newNode.value = item;
                newNode.right = newNode;    
            }
        }else if (value.compareTo(item) < 0) {
            if (left != null) {
                add(left.value);
            }
          } else {
            BinarySearchTree<E> newNode = new BinarySearchTree<E>();
            newNode.value = item;
            newNode.left = newNode;
        }
    }

This seems to only add the root value of 5. I believe it has something to do with not connecting the new "node" to the parent or maybe my constructor. I am struggling to traverse the tree and connect the "nodes" without using a node class.

try to use right.add(item); and left.add(item) instead of add(left.value); — Alberto
– Alberto, Commented Nov 20, 2019 at 0:02
I just noticed you have a method called isRoot() that you didn't include... How does it work? — LowKeyEnergy
– LowKeyEnergy, Commented Nov 20, 2019 at 3:26
@LowKeyEnergy it checks if(parent == null); the root doesn't have a parent so it returns true if the node is the root. The code works now after fixing the recursion statement. — slb
– slb, Commented Nov 20, 2019 at 3:38

LowKeyEnergy · Accepted Answer · 2019-11-20 00:22:44Z

1

Look at it this way... Every node of a binary tree is itself a binary tree.

If you consider the two as equivalent, then your BinarySearchTree class is actually a Node class... it's just not named "Node" .

Any time you want to use an object of class Node, just declare it as a BinarySearchTree Instead.

Instead of having:

Node left;
Node right;

You will have:

BinarySearchTree left;
BinarySearchTree right;

And by the way, what you are missing is this:

this.left = newNode;

or

this.right = newNode;

It means that the BinarySearchTree is setting the left or the right variable of itself. That's what this means.

As it turns out, the this is not even necessary except in some cases where the context is ambiguous. In your case, you can just say:

left = newNode;

or

right = newNode;

edited Nov 20, 2019 at 0:22

answered Nov 20, 2019 at 0:13

LowKeyEnergy

6534 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

slb Over a year ago

thank you! I had realized that I wasn't setting the left and right to my new node but it seems like where ever I add that statement into my add method it causes a StackOverflowError.

LowKeyEnergy Over a year ago

Stack overflow indicates that endless recursion is occurring. Any time you make a recursive call, you need to be sure that the call you make is solving a smaller "problem" than the recursive call you are in.

Collectives™ on Stack Overflow

How to add to a Binary Search Tree without using a Node class

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related