CODEWITHSUNDEEP
javabinary-search-treenodespretty-print
roughosing
roughosing

Reputation: 71

Pointer issue with Binary Search tree when trying to print

Im writing the method to print a binary search tree in order. I figured out a way to do this but it requires either the deletion or nullify nodes as they are printed. Below is my code:

public String printKeysInOrder() {
        String output = "";
        if (isEmpty()) return "()";
        else{
            int i = 0;
            while(i!=size()){
                Node x = root;
                int loopBreak = 0;
                while(loopBreak!=1){
                    if(x.left != null) x = x.left;
                    else if (x.right != null){
                        output = output + " " + x.val;
                        x.key = null;
                        x = x.right;
                        i++;
                    }
                    else{
                        output = output + " " + x.val;
                        x.key = null;
                        loopBreak = 1;
                    }
                }
                i++;
            }
        }
        return output;
    }

for the tree:

            _7_
          /     \
        _3_      8
      /     \
     1       6
      \     /
       2   4
            \
             5

it should print "1 2 3 4 5 6 7 8"

the code works in a way that it favors moving left through the tree until it can no longer go left, it then stores that node's value in the string output, makes the nodes key equal to null (as so future iterations of the loop do not go down that tree) and moves right if possible or iterates back around the loop.

Although i'm having trouble making it so the node equals null, as when the code is executed (via junit test) the code doesnt recognize that null key and goes through that subtree anyway? Can anyone help me out or tell me how to make it so the x.left and x.right pointers on future iterations recognize the node as null?

Upvotes: 0

Views: 103

Answers (1)

Alain O'Dea
Alain O'Dea

Reputation: 21686

You don't need to nullify or delete nodes you need a traversal algorithm.

The in-order traversal provided here should work without major modification: http://www.javabeat.net/binary-search-tree-traversal-java/

Another object-oriented approach to this is a Visitor supplied to an in-order traversable which allows you to supply the action performed at each node whether it be printing, collecting, mapping, or something else.

Upvotes: 1

Related Questions