CODEWITHSUNDEEP
javaalgorithmtreebinary-search-treeinorder
parth
parth

Reputation: 272

InOrder traversal goes in infinite loop and prints only first node

I was trying to write a simple piece of code to traverse a binary search tree with inorder traversal.I was able to right the insertion code perfectly as the debugger showed a tree exactly like I wanted.But my recursive traversal isnt giving out the correct results.Here's a screenshot of my debugger:

Left Subtree followed by Right subtree

Left

Right Subtree

which corresponds to the following visualized tree:

Binary Tree

Instead of printing out all nodes,it just prints the first element(39) in an infinite loop. Here's my code: Main.java

public class Main {

public static void main(String[] args) {
   BinaryTree binaryTree = new BinaryTree();
    binaryTree.add(50);
    binaryTree.add(40);
    binaryTree.add(39);
    binaryTree.add(42);
    binaryTree.add(41);
    binaryTree.add(43);
    binaryTree.add(55);
    binaryTree.add(65);
    binaryTree.add(60);
    binaryTree.inOrderTraversal(binaryTree.root);
}
}

Node.java

public class Node {
int data;
Node left;
Node right;
Node parent;


public Node(int d)
 {
   data = d;
   left = null;
   right = null;
 }
}

BinaryTree.java

public class BinaryTree {
Node root = null;
public void add(int d)
{
    Node newNode =  new Node(d);
    if(root!=null)
    {


        Node futureParent = root;
        while(true)
        {
        if(newNode.data < futureParent.data)      //going left
        {
            if(futureParent.left == null)
            {
                futureParent.left = newNode;
                newNode.parent = futureParent;
                break;
            }
            futureParent = futureParent.left;

        }
        else
        {
            if(futureParent.right == null)
            {
                futureParent.right = newNode;
                newNode.parent = futureParent;
                break;
            }
            futureParent = futureParent.right;
        }

        }

    }
    else
    {
        root = newNode;
    }
}
public void inOrderTraversal(Node node)
{
    while(node!=null)
    {
    inOrderTraversal(node.left);
    System.out.println(node.data);
    inOrderTraversal(node.right);
    }
}
}

Upvotes: 0

Views: 1192

Answers (2)

Amudhan
Amudhan

Reputation: 725

When you are using recursion, you should remember the base case, reduced problem, and general solution.

The base case here is: if node == null, stop recursion. Reduced Problem is: Should be able to visit any single left/parent/right node General Solution is: Visit Left, Visit Node, Visit Right.

So, your code should be:

public void lnrTraverse(Node node) {
    //if (node == null) return; //This is not needed. Valid only if it an empty tree
    if (node.left != null) {
        lnrTraversal(node.left);
    }
    System.out.println(node);
    if (node.right != null) {
        lnrTraversal(node.right);
    }
}

Upvotes: 0

anonymous
anonymous

Reputation: 1317

You don't need the while() loop in your inOrderTraversal(). It is a recursive call. It's causing an endless loop.

However, you do need something to stop the recursion. You only recurse if the node is not null.

public void inOrderTraversal(Node node) {
    if(node==null) return;

    inOrderTraversal(node.left);
    System.out.println(node.value);
    inOrderTraversal(node.right);
}

Upvotes: 3

Related Questions