CODEWITHSUNDEEP
javarecursionbinary-search-tree
Chris
Chris

Reputation: 2274

Traverse Binary Search Tree Pre Order recursively

I am trying to traverse a BST Pre-Order recursively but I can not make it work. This is what I've tried:

public String PreOrder() {
    return preOrderStringBuild(root, "");
}

public String preOrderStringBuild(Node root, String preOrderString) {
    if (root == null) {
        return "";
    }

    preOrderString += root.key + " "; 
    preOrderStringBuild(root.left, preOrderString);
    preOrderStringBuild(root.right, preOrderString);            

    return preOrderString;
}

But this only gives me the first Element... What am I doing wrong here?

Upvotes: 0

Views: 63

Answers (1)

Joni
Joni

Reputation: 111219

In Java, method parameters are passed by value, and strings are immutable.

That means that this line of code does not change the string that is passed into the method, instead it creates a new string, that can only be seen in the current call of the method:

preOrderString += root.key + " ";

One way to fix this is to use a mutable string type like StringBuilder instead of String. Changes to mutable objects are visible outside the method.

public String preOrderStringBuild(Node root, StringBuilder preOrderString) {
    ...
    preOrderString.append(root.key + " "); // instead of preOrderString = ...
    ...

Another way is to way to fix this is make sure you use the value returned from the recursive calls. Going by this route you don't even need to pass in the string you are building.

public String preOrderStringBuild(Node root) {
    if (root == null) {
        return "";
    }

    String preOrderString = root.key + " " 
        + preOrderStringBuild(root.left) 
        + preOrderStringBuild(root.right);

    return preOrderString;
}

Upvotes: 1

Related Questions