CODEWITHSUNDEEP
javarecursionpreorder
Kyle
Kyle

Reputation: 1

Preorder transversal of a binary tree is printing out extra values I do not want

I have implemented a preorder transversal in Java that prints out the character at each node of a binary tree along with the path represented by 0s and 1s to get to that node. "0" meaning to go down a left path and "1" to go down the right. However, after certain nodes are printed it will print extra path numbers before printing the next character at a different node. This is my code

public static void printCodes(MsgTree root, String code)
    {
        if (root == null) {
            return;
        }
        
        System.out.println("   " + root.payloadChar + "        " + code);

        printCodes(root.left, code + "0");
        
        printCodes(root.right, code + "1");
    }

The result should look like

a   0
!   100
d   1010
c   1011
r   110
b   111

but it instead looks like

a   0
    1
    10
!   100
    101
d   1010
c   1011
    11
r   110
b   111

I have tried a ton of different things, but nothing seems to work. Any help is much appreciated!

Upvotes: 0

Views: 172

Answers (1)

Willis Blackburn
Willis Blackburn

Reputation: 8204

The issue is that in your tree (which I recognize from another question!) nodes either hold data, or they hold children, but not both.

Look at the second line of the desired output:

!   100

That means that in order to get to the ! node, the program had to go right (1) then left twice (00). So it visited a couple of other nodes in the process of getting to ! but didn't print them.

You should just check if payloadChar is empty and if it is, don't print anything.

By the way, although you didn't include it, I'm pretty sure that your output included a blank line above the first one:

(blank line)
a   0 
    1
    10
!   100

That would have come from the root node.

Upvotes: 1

Related Questions