CODEWITHSUNDEEP
javadata-structurestreebinary-tree
Anuvrat Tiku
Anuvrat Tiku

Reputation: 1646

Preorder traversal of a binary tree. If vs while

I am trying to figure out why the console output get stuck in an infinite loop at the leaf when I use while in place of if in the code below.

void preOrder(Node root) {
    Node n = root;
    while(n != null) {
        visit(n);
        preOrder(n.left);
        preOrder(n.right);
        }
    }

When the recursive function for preOrder is called at the leaf, the leaf has no left child.Shouldn't the execution stop there.

Upvotes: 1

Views: 518

Answers (2)

Konstantin Yovkov
Konstantin Yovkov

Reputation: 62864

The problem is that when having while(n != null), you never reassign n to something that could potentially be not null and thus you get an infinite loop.

An if statement is what you need, because you already have recursive calls, which will traverse the tree up until a leaf is found:

Node n = root;
if (n != null) {
    visit(n);
    preOrder(n.left);
    preOrder(n.right);
}

Upvotes: 3

Eran
Eran

Reputation: 393781

while(n != null) will either always be true or never be true, since the body of the loop doesn't change the value of n. Therefore, the loop will either never execute or be infinite.

Since you are using recursion, you don't need a loop.

void preOrder(Node root) {
    Node n = root;
    if (n != null) {
        visit(n);
        preOrder(n.left);
        preOrder(n.right);
    }
}

When the recursive function for preOrder is called at the leaf, the leaf has no left child.Shouldn't the execution stop there

Well, the execution of preOrder(n.left) will terminate (since n.left is null), but then it will return to the previous preOrder call, and call preOrder(n.right), and if that call terminates, it will then be stuck in the infinite while loop.

Upvotes: 3

Related Questions