CODEWITHSUNDEEP
javadata-structuresbinary-search-treeabstract-data-type
super_user
super_user

Reputation: 143

Recursive Preorder traversal running untill stack overflows, (BST) in JAVA

I am implementing simple Binary Search Tree in java with insert and preorder methods. I am running into infinite preorder execution until stackoverflows.

Here is the Node class : 

public class Node {
private Node right, left;
private int data;

public Node(Node right, Node left, int data) {
    super();
    this.right = right;
    this.left = left;
    this.data = data;
}

public Node() {
    super();
    this.right = this.left = null;
    this.data = 0;
}

public Node getRight() {
    return right;
}

public void setRight(Node n) {

    this.right = n;
}

public Node getLeft() {
    return left;
}

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

public int getData() {
    return data;
}

public void setData(int data) {
    this.data = data;
}

}

Here is the BinarySearchTree Class : 

public class BinarySearchTree {

private Node root;

public BinarySearchTree() {
    root = null;
}

public Node insert(int data) {
    root = insertInto(root, data);
    return root;
}

private Node insertInto(Node node, int data) {

    if (node == null) {
        Node temp = new Node();
        temp.setData(data);
        return temp;
    } else if (data < node.getData()) {

        node.setLeft(insertInto(node.getLeft(), data));

    } else if (data > node.getData()) {

        node.setRight(insertInto(node.getRight(), data));

    }

    return root;
}

public void preorder() {
    getPreorder(root);
}

private void getPreorder(Node root) {
    if (root == null)
        return;
    System.out.println(root);
    getPreorder(root.getLeft());
    getPreorder(root.getRight());
}
}

Here is the main class : 

public class BstMain {

public static void main(String args[])
{
    BinarySearchTree bst = new BinarySearchTree();

    bst.insert(10);

    bst.insert(9);

    bst.insert(15);

     bst.insert(8);
     bst.insert(20);
     bst.preorder();

}
}

Here is the output : 

Node [data=10]
Node [data=10]
Node [data=10]
Node [data=10]
Node [data=10]
Node [data=10]
Node [data=10]
Node [data=10]
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.SingleByte.withResult(Unknown Source)
at sun.nio.cs.SingleByte.access$000(Unknown Source)
at sun.nio.cs.SingleByte$Encoder.encodeArrayLoop(Unknown Source)
at sun.nio.cs.SingleByte$Encoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
at sun.nio.cs.StreamEncoder.write(Unknown Source)
at java.io.OutputStreamWriter.write(Unknown Source)
at java.io.BufferedWriter.flushBuffer(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at java.io.PrintStream.print(Unknown Source)
at java.io.PrintStream.println(Unknown Source)
at bsTree.BinarySearchTree.getPreorder(BinarySearchTree.java:42)
at bsTree.BinarySearchTree.getPreorder(BinarySearchTree.java:43)
at bsTree.BinarySearchTree.getPreorder(BinarySearchTree.java:43)
at bsTree.BinarySearchTree.getPreorder(BinarySearchTree.java:43)

I think there's something wrong with insertion logic, can't figure out what is it.

Upvotes: 0

Views: 96

Answers (1)

gpeche
gpeche

Reputation: 22514

The problem is in insertInto(...):

} else if (data < node.getData()) {

    node.setLeft(insertInto(node.getLeft(), data));

} else if (data > node.getData()) {

    node.setRight(insertInto(node.getRight(), data));

}

return root;

In any of these two cases, you end up setting the left / right child to the root node, so you are creating a cycle. That is what causes the infinite recursion.

Upvotes: 2

Related Questions