CODEWITHSUNDEEP
javarecursionbinary-search-tree
IceTea
IceTea

Reputation: 650

Need help understanding a traverse Binary Search Tree method

I came across a traversing binary search tree function but I can't wrap my head around it. Here's the code:

public void inOrderTraverseTree(Node focusNode){
    if(focusNode != null){
        inOrderTraverseTree(focusNode.leftChild);
        System.out.println(focusNode);
        inOrderTraverseTree(focusNode.rightChild);
    }
}

Assuming a "two-levels" balanced binary search tree, this is how I understand this recursive method:

But it supposedly works (https://www.youtube.com/watch?v=M6lYob8STMI). Can anyone point out where I've gone wrong?

Upvotes: 0

Views: 88

Answers (3)

The Scientific Method
The Scientific Method

Reputation: 2436

However, since root.leftChild has no leftChild --> focusNode.leftChild == null, the if loop will not run

No, it will. since it is recursive it will continue doing for previous calls, check for righchild node in this case.

watch the call order of the function:

enter image description here

it continues ...

Upvotes: 0

codeLover
codeLover

Reputation: 2592

You need to understand the basic recursion and binary search tree structure here. Lets take below tree to understand this algorithm:

enter image description here Steps:

1. Focus Node is 9 , since it is not null, thus , inOrderTraverseTree
is invoked with focus node as 7(with left node to 9)
2. Focus Node is 7 , since it is not null, thus , inOrderTraverseTree is invoked with focus node as null(with left
node to 7)
3. Focus Node is null , thus , if condition is not satisfied and execution of function call at step 2 continues.
4. Control goes to method call with node as 7 (since left node was blank) and 7 is printed at System.out.println statement.
5. Now  inOrderTraverseTree for focus node null is invoked (with right node to 7)
6. Focus Node is null , thus , if condition is not satisfied and execution of function call at step 2 continues.
7. inOrderTraverseTree for focus node 2 exits and control goes to method call with node as 9.
8. Control goes to method call with node as 9  and 9 is printed at System.out.println statement.
9. inOrderTraverseTree for focus node 11 is invoked (with right node to 9)
10.inOrderTraverseTree for focus node null is invoked (with left node to 11), thus, if condition is not satisfied and control is sent
back to step 9
11. Control goes to method call with node as 11  and 11 is printed at System.out.println statement.
12.inOrderTraverseTree for focus node null is invoked (with right node to 11), thus, if condition is not satisfied and control is sent
back to step 9.

And the execution ends

Upvotes: 0

Susmit Agrawal
Susmit Agrawal

Reputation: 3764

The logic applied here:

  1. Check the focused node. If null then return to parent's inOrderTraverseTree. But since nothing happens after the check for null, an additional return statement is same as no statement at all.

  2. If not null, repeat from (1) for the left child node.

  3. Print the value of the focused node.

  4. Repeat from (1) for the right child node.

  5. Return from current node's inOrderTraverseTree to parent node's inOrderTraverseTree.

Of course, if the focused node is the root node, inOrderTraverseTree simply returns to main, or the method that first invoked it

As an example, consider the tree below:

            A
          /   \
         B     C
        / \   / \
       D   E F   G

Trace:

A->inOrderTraverseTree(left)
    B->inOrderTraverseTree(left)
        D->inOrderTraverseTree(left) //null, return to D
        print(D)
        D->inOrderTraverseTree(right) //null, return to D
        return to B

    print(B)

    B->inOrderTraverseTree(right)
        E->inOrderTraverseTree(left) //null, return to E
        print(E)
        E->inOrderTraverseTree(right) //null, return to E
        return to B

    return to A

print(A)

A->inOrderTraverseTree(right)
    //Continue for the right subtree.

Upvotes: 3

Related Questions