Issues with Binary TreeNode editing function

Question

I'm having some trouble with my code.

This function's purpose is to traverse through a binary tree and edit it such that branches from a certain point are replaced by new ones housed under the "newNode". Currently, it returns the same value for the tree that it started with (so the current = newNode doesn't actually edit the original tree).

Can anyone explain why this is? Thanks.

 public static Node editTree(Node current, Node newNode, String value) {
        if (current == null) {
            return null;
        }

        if (current.value.equals(value)) {
            current = newNode;
            return current;
        }

        if (!current.isLeaf()) {
            editTree(current.getLeft(), newNode, value);
            editTree(current.getRight(), newNode, value);
            return current;
        }

        return current;
    }

This has to be accomplished in such a way that a tree (the original tree) is first traversed until a certain value is found. Then the node that houses the value is entirely replaced with a new node, which contains its own value and its own left and right nodes. A global variable Node is then set to be equal to the value of the newly edited tree, which is then used to reset the original trees value. The reason it can't be done any other way is because I can't set the values of the left and right nodes in the node class, since it's not permitted.

Another likely source of error: `if (current.value == value)`- you should check equality, not identity (`if (current.value.equals(value))`) — Martin Schneider, Feb 11 '19 at 05:55
Makes no difference to how the function performs, I've already edited this same function so that 1) it had no isLeaf() check, 2) every comparison used .equals() and 3) it had fewer returns. Nothing has yielded the results wanted so far. — , Feb 11 '19 at 05:58
Yeah sure, the reason was outlined by Kartik in his Answer. But nevertheless, you should also fix the above condition because otherwise you might never enter that branch and return the new `current`. — Martin Schneider, Feb 11 '19 at 06:04
I've amended it, but I still don't know how to resolve the issue... — , Feb 11 '19 at 06:05

score 1 · Answer 1 · answered Feb 11 '19 at 05:48

1

In the line current = newNode; you are just changing the reference of the current variable in your method. It won't affect the original tree. You need to set newNode as a value to the previous node.

For more information, see Is Java “pass-by-reference” or “pass-by-value”?

answered Feb 11 '19 at 05:48

Kartik

7,677
4
28
50

I can't do that. The original node class doesn't allow you to add any left or right nodes to any node, it only allows you to edit the actual value (which is a String), hence the only way to edit the tree is to create another tree and have that one be edited through the use of the function above, and then set the old tree equal to the new tree. – Feb 11 '19 at 05:52

Maurice Perry · Answer 2 · 2019-02-11T07:06:26.130

Assigning a new value to current will have no effect outside of the method. I think you should use the return value:

public static Node editTree(Node current, Node newNode, String value) {
        if (current == null) {
            return null;
        }

        if (current.value.equals(value)) {
            return newNode;
        }

        if (!current.isLeaf()) {
            current.setLeft(editTree(current.getLeft(), newNode, value));
            current.setRight(editTree(current.getRight(), newNode, value));
        }

        return current;
    }

UPDATE: Complete code, and test results

public class Node {
    public final String value;
    private Node left;
    private Node right;

    Node(String value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public boolean isLeaf() {
        return left == null && right == null;
    }

    @Override
    public String toString() {
        return "Node{" + "value=" + value + ", left=" + left + ", right=" + right + '}';
    }
}

Test method:

public static void main(String[] args) {
    Node tree = new Node("b",
            new Node("a", null, null), new Node("c", null, null));
    System.out.println(tree);
    tree = editTree(tree, new Node("d", null, null), "c");
    System.out.println(tree);
}

Results:

Node{value=b, left=Node{value=a, left=null, right=null}, right=Node{value=c, left=null, right=null}}
Node{value=b, left=Node{value=a, left=null, right=null}, right=Node{value=d, left=null, right=null}}

That will only return the newNode tho... I'm trying to return a fully edited tree that now containes the newNode, not just the newNode (which I passed into the function as an argument in the first place) — , Feb 11 '19 at 06:45
@TrojanTheHorse that's exactly what it does (because the method is recursive) — Maurice Perry, Feb 11 '19 at 06:47
Well, for one, I can read the code and see it wont work. Two, just to humor you, I modified the code so that it's now identical to yours and it performs exactly as it did before. — , Feb 11 '19 at 06:57
@TrojanTheHorse Well, perhaps you need glasses. See my update. — Maurice Perry, Feb 11 '19 at 07:07
Cant have set methods... (wouldn't have even been an issue if I could use setters to append the new node) — , Feb 11 '19 at 14:40
@TrojanTheHorse if you can't have any setter, the only option is to rebuild the whole tree, isn't it? — Maurice Perry, Feb 18 '19 at 06:59

Issues with Binary TreeNode editing function

2 Answers2