CODEWITHSUNDEEP
javadata-structurestreestack-overflow
salty_coffee
salty_coffee

Reputation: 631

toString causing StackOverflow error

I overrode my toString() in my Node class for a BinaryTree. Now it causes a StackOverflow and I cant figure out why.

My BinaryTree.Java file isn't complete, but it works for what iv completed up to this point.

So basically, if I include the overridden toString() in Node.java my code breaks. and I'm lost as to why. I was thinking somehow the toString() is recursively calling Nodes somehow

full code:

Node.Java

public class Node {
    Node right;
    Node left;
    String element;
    Node parent;

    public Node(){  

    }

    public Node(String element){
        this.element = element;

    }

    public String getElement(){
        return element;
    }

    public Node getLeft(){
        return left;
    }

    public Node getRight(){
        return right;
    }

    public void setElement(String str){
        element = str;
    }

    public void setRight(Node right){
        this.right = right;
    }

    public void setLeft(Node left){
        this.left = left;
    }

    public void setParent(Node parent){
        this.parent = parent;
    }

    public Node getParent(){
        return parent;
    }

    @Override
    public String toString() {
        return "Node [right=" + right + ", left=" + left + ", element=" + element + ", parent=" + parent + "]";
    }

}

BinaryTree.Java

import java.util.ArrayList;

public class BinaryTree {
    Node root;
    ArrayList<Node> tree = new ArrayList<>();


    //create a tree with a root node, and two empty nodes
    //root has no data
    public BinaryTree(Node root){
        tree = new ArrayList<>();
        this.root = root;
        root = new Node();  //parent of root will be set to null
        tree.add(root); // root at position 1 in arrayList
    }


    public BinaryTree(){

    }


    //assuming one of the children are null and there is a root
    public void insertNode(Node insertNode, Node parent){
        //setthis nodes parent to parent index.



        tree.add(insertNode); // add the node to end of the arraylist.
        insertNode.setParent(parent);  //sets the nodes parent node
        //if parents left is null, 
        if (parent.getLeft()==null){
            parent.setLeft(insertNode);
        }

        //else, its right is null
        else{
            parent.setRight(insertNode);
        }

    }

    public void insertRoot(Node node){
        if (tree.isEmpty()){  //add the root
            root = node;
            tree.add(node);

        }
        else{tree.add(node);}// add it, get its location in tree and then get its parent.
        //int index = tree.indexOf(node);// found the index of the nod  
    }


    public boolean isEmpty(){
        return root==null;
    }

    @Override
    public String toString() {
        return "BinaryTree [root=" + root + ", tree=" + tree + ", isEmpty()=" + isEmpty() + "]";
    }
}

TreeTest.java

public class TreeTest {



    public static void main(String[] args){
        //create empty tree & test
        BinaryTree myTree = new BinaryTree();
        System.out.println(myTree.isEmpty());
        System.out.println(myTree.toString());

        //create root node & test
        Node myRoot = new Node();  //Node@7852e922
        myTree.insertRoot(myRoot);
        myRoot.setElement("foo");
        System.out.println(myTree.isEmpty());
        System.out.println(myTree.toString());
        System.out.println(myTree.isEmpty());
        System.out.println(myTree.toString());


        //create a child node and test
        Node secondNode = new Node();  //Node@4e25154f
        myTree.insertNode(secondNode, myRoot);
        System.out.println(myTree.toString());   //code breaks here
        System.out.println(myRoot.getLeft());

    }}

Upvotes: 2

Views: 2208

Answers (3)

alayor
alayor

Reputation: 5035

Print the parent's element instead of the entire object which would call toString() again.

 @Override
 public String toString() {
    return "Node [right=" + right + ", left=" + left + ", element=" +
              element + ", parent=" + parent.element + "]";
 }

Upvotes: 1

luk2302
luk2302

Reputation: 57154

return "Node [... parent=" + parent + "]";

What does the parent print? 

return "Node [right=" + right + ", left=" + left + "..."]";

What do left and right print? 

return "Node [... parent=" + parent + "]";

Continue as needed...

Solution: do not print the parent.

Your node A prints its content and in converting itself to a String tries to convert parent to a String. Its parent P then goes ahead and converts itself to a String by converting its left and right child to a String, one of those children is once again A. And you are back in the beginning of the paragraph.

Upvotes: 3

Andy
Andy

Reputation: 151

Looking at your toString() method, I think you're right about the recursive call.

Imagine some node A has a child B. Then in order for A to print its output, it needs to print the child node B. In order for B to print its output, it needs to print the parent node A. In order for A to print its output, it needs to print the child node B, and so on.

You might change the toString() to print out just the parent's element, which would stop the loop.

Upvotes: 4

Related Questions