Display Binary Search Tree in Java

Question

I am having trouble displaying a binary search tree

I want to be able to see every value that was inserted into the tree and I am not sure where the error is located. Also is there anything that I should change to make this code more functional or easier to read?

class BSTNode {
    public int value; // data item (key)
    public BSTNode leftChild; // this node's left child
    public BSTNode rightChild; // this node's right child

    public void displayNode() // display this node
    {
        StringBuilder node = new StringBuilder();
        node.append("{");
        node.append(value);
        node.append("}");
        System.out.println(node);
    }
}

class BSTree {
    private BSTNode root; // first node of tree

    public BSTree() {
        root = null;
    }

    public BSTNode find(int searchValue) // looks for node with certain key
    {
        BSTNode current = root;

        while (current.value != searchValue) {

            if (searchValue < current.value)
                current = current.leftChild;
            else
                current = current.rightChild;

            if (current == null)
                return null;
        }
        return current;
    }

public void insert(int value) // insert a new Node
{
    BSTNode newNode = new BSTNode();
    BSTNode current, parent;

    newNode.value = value;

    if (root == null)
        root = newNode;
    else {
        current = root;
        while (true) {
            parent = current;
            if (value < current.value) // go left
            {
                current = current.leftChild;
                if (current == null) // if end of line
                {
                    parent.leftChild = newNode;
                    return;
                }
            } // end left
            else // go right
            {
                current = current.rightChild;
                if (current == null) // if end of the line
                {
                    parent.leftChild = newNode;
                    return;
                }
            }
        }
    }
}

Here is the display method:

public void displayBSTree() // display search tree
{
    Stack<BSTNode> treeStack = new Stack<BSTNode>();
    treeStack.push(root);
    int numOfBlanks = 32;
    boolean isRowEmpty = false;
    System.out.println("\n");

    while (isRowEmpty == false) {
        Stack<BSTNode> localStack = new Stack<BSTNode>();
        isRowEmpty = true;

        for (int x = 0; x < numOfBlanks; x++)
            System.out.print(" ");

        while (treeStack.isEmpty() == false) {
            BSTNode temp = (BSTNode)treeStack.pop();
            if (temp != null)
            {
                System.out.print(temp.value);
                localStack.push(temp.leftChild);
                localStack.push(temp.rightChild);

                if (temp.leftChild != null || temp.rightChild != null)
                    isRowEmpty = false;
            }
                else {
                    System.out.print("--");
                    localStack.push(null);
                    localStack.push(null);
                }

                for (int y = 0; y < numOfBlanks*2-2; y++)
                    System.out.print(" ");
            }
        System.out.println();
        numOfBlanks /= 2;
        while (localStack.isEmpty() == false)
            treeStack.push(localStack.pop());

    }
    System.out.println();
}

and the main method

public class ShowBST {

    public static void main(String[] args) {
        int[] values = new int[] {23, 17, 5, 90, 12, 44, 38, 84, 77, 3, 66, 55, 1, 19, 37, 88, 8, 97, 25, 50, 75, 61, 49};

        BSTree tree = new BSTree();

        for (int value : values) {
            tree.insert(value);
        }
        tree.displayBSTree();

    }

}

Currently the output is

                            23                                                              
            49                              --

Have you considered representing this as nodes in a JTree? Or do you need this printed to screen as you have it now using only System.out.print() ? — Constantin
– Constantin, Commented Jul 12, 2015 at 19:10

franklynd · Accepted Answer · 2015-07-12 19:28:21Z

1

The else condition in insert adds the node to the leftChild instead of rightChild.

        else // go right
        {
            current = current.rightChild;
            if (current == null) // if end of the line
            {
                parent.leftChild = newNode;
                return;
            }
        }

After you fix that you need to adjust your spacing, you run out of blanks on all the nulls so numbers start getting merged together.

answered Jul 12, 2015 at 19:28

franklynd

1,9603 gold badges13 silver badges12 bronze badges

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

Comments

Caleb An · Accepted Answer · 2015-07-12 19:22:54Z

In your traversal of the tree in your insert method, you accidentally go left instead of going right:

 else // go right
        {
            current = current.rightChild;
            if (current == null) // if end of the line
            {
                parent.leftChild = newNode;
                return;
            }
        }

to fix, change the reference of parent.leftChild to parent.rightChild.

In addition, there improvements to your code that can be made. For example, create a constructor with a parameter for the BSTNode class so that you do not have to set .value each time. Like so:

class BSTNode {
    //constructor 
    public BSTNode(int value){
    this.value = value; 
    }
}

Then change to BSTNode newNode = new BSTNode(value);

Juan · Accepted Answer · 2015-07-12 19:18:32Z

I guess it is a copy & paste error:

            else // go right
            {
                current = current.rightChild;
                if (current == null) // if end of the line
                {
                    parent.leftChild = newNode;
                    return;
                }
            }

Should be:

            else // go right
            {
                current = current.rightChild;
                if (current == null) // if end of the line
                {
                    parent.rightChild = newNode;
                    return;
                }
            }

You are overriding the left node every time you find something suitable as a right node, that's why you can only see the fist node added (23) and the last (49) which should be going to the right but it appears to be in the left.

Collectives™ on Stack Overflow

Display Binary Search Tree in Java

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related