Transferring a String array to Binary Tree

Question

I'm trying to write a method that can transfer an array into a Binary tree. I know the code is not right, I run it and hope it would show something that I can continue to fix it. But it just kept loading without any error or result. May anyone give me some advice, please! Here is the BST class:

public class BSTNode {
    private String data;

    private BSTNode left;
    private BSTNode right;

    public BSTNode(String data) {
        this.data = data;
        this.right = null;
        this.left = null;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public BSTNode getLeft() {
        return left;
    }

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

    public BSTNode getRight() {
        return right;
    }

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

And my method:

public BSTNode fromArray(String[] array, int start, int end) {
    int i = start;
    BSTNode root = new BSTNode(array[i]);
    BSTNode current = root;
    BSTNode parent = null;
    while (i <= end) {
        if (array[i].compareTo(current.getData()) < 0) {
            parent = current;
            current.setLeft(current); //Should I put current.setLeft(root) here?
        } else {
            parent = current;
            current.setRight(current);
        }
        // Create the new node and attach it to the parent node
        if (array[i].compareTo(parent.getData()) < 0) {
            parent.setLeft(new BSTNode(array[i]));
        } else {
            parent.setRight(new BSTNode(array[i]));
        }
        i++;
    }
    return current;
}

Thank you for your time!

current.setLeft(current); and current.setRight(current); basically link the current node to itself which can cause an endless loop. Those calls don't make sense at all. Try to explain what your intention is with this piece of code and it should become obvious what should happen. Additionally, you're never changing current in the loop and thus parent will also never change. — Thomas
– Thomas, Commented Nov 30, 2021 at 7:20
I see that why it kept loading. I try to make it turn left while 2 variable comparison <0 and turn right if >0. I researched some sample code they just simple put current.left or current.right. But it didn't work in my case so I thought setLeft would work. I don't know how to declare it in a correct way. Thank you for the help! — Tobi
– Tobi, Commented Nov 30, 2021 at 8:55

Oleg Cherednik · Accepted Answer · 2021-11-30 09:11:12Z

3

After you've initialized the root, you've already inserted the first element, so you can increment i right away.

You set the left and right pointers without keeping track of the prior value.

You never change the value of current within the loop, and, as you immediately assign it to parent, you don't change parent either.

You should return the root instead of the current node.

How about something like this:

    while (++i <= end) {
        current = root;
        while (current != null) {
            parent = current;
            if (array[i].compareTo(current.getData()) < 0) {
                current = current.getLeft();
            } else {
                current = current.getRight();
            }
        }
        // Create the new node and attach it to the parent node
        if (array[i].compareTo(parent.getData()) < 0) {
            parent.setLeft(new BSTNode(array[i]));
        } else {
            parent.setRight(new BSTNode(array[i]));
        }
    }
    return root;

UPDATE:

You can avoid a redundant comparison by keeping its result in a variable:

    while (++i <= end) {
        boolean left;
        current = root;
        do {
            parent = current;
            left = array[i].compareTo(current.getData()) < 0;
            if (left) {
                current = current.getLeft();
            } else {
                current = current.getRight();
            }
        } while (current != null);
        // Create the new node and attach it to the parent node
        if (left) {
            parent.setLeft(new BSTNode(array[i]));
        } else {
            parent.setRight(new BSTNode(array[i]));
        }
    }
    return root;

edited Nov 30, 2021 at 9:11

Oleg Cherednik

18.3k4 gold badges25 silver badges38 bronze badges

answered Nov 30, 2021 at 7:20

Maurice Perry

9,6782 gold badges15 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Maurice Perry Over a year ago

Note that you should also check that start <= end at the beginning, and return null otherwise.

Maurice Perry Over a year ago

start and end are both inclusive actually (I would rather have end exclusive, but it's not in the question.)

Maurice Perry Over a year ago

@sadetaosa please read my answer before posting comments

Tobi Over a year ago

Thanks a lot for the answer. It really helpful to me!. I'll test it tmr and will update if it runs well!

Thomas Over a year ago

On a side note, the entire loop body is basically just the add(value) method, i.e. you could move that code to a separate method and then just call it like add(array[i]).

Oleg Cherednik · Accepted Answer · 2021-11-30 09:10:25Z

public class Main {

    public static final class Node {

        public static final String NULL = "_";
        public static final String SPLIT = ",";

        private final String val;
        private Node left;
        private Node right;

        public Node(String val) {
            this.val = val;
        }

    }

    public static void main(String... args) {
        Node root = createBinaryTree();
        String str = serialize(root);   // 0,1,3,7,_,9,_,_,_,4,_,_,2,5,_,8,_,_,6,_,_
        Node newRoot = deserialize(str);
    }

    private static String serialize(Node root) {
        StringBuilder buf = new StringBuilder();
        serialize(root, buf);
        return buf.toString();
    }

    private static void serialize(Node node, StringBuilder buf) {
        if (buf.length() > 0)
            buf.append(Node.SPLIT);

        if (node == null)
            buf.append(Node.NULL);
        else {
            buf.append(node.val);
            serialize(node.left, buf);
            serialize(node.right, buf);
        }
    }

    private static Node deserialize(String str) {
        String[] values = str.split(Node.SPLIT);
        return deserialize(values, new AtomicInteger());
    }

    private static Node deserialize(String[] values, AtomicInteger i) {
        if (i.get() >= values.length)
            return null;

        String value = values[i.getAndIncrement()];

        if (Node.NULL.equalsIgnoreCase(value))
            return null;

        Node node = new Node(value);
        node.left = deserialize(values, i);
        node.right = deserialize(values, i);

        return node;

    }

    /*
     *         0
     *       /  \
     *      1    2
     *     / \  / \
     *    3  4 5  6
     *   /      \
     *  7        8
     *   \
     *    9
     */
    private static Node createBinaryTree() {
        Node[] nodes = { new Node("0"), new Node("1"), new Node("2"), new Node("3"),
                new Node("4"), new Node("5"), new Node("6"), new Node("7"),
                new Node("8"), new Node("9") };

        nodes[0].left = nodes[1];
        nodes[0].right = nodes[2];
        nodes[1].left = nodes[3];
        nodes[1].right = nodes[4];
        nodes[2].left = nodes[5];
        nodes[2].right = nodes[6];
        nodes[3].left = nodes[7];
        nodes[5].right = nodes[8];
        nodes[7].right = nodes[9];

        return nodes[0];
    }


}

Collectives™ on Stack Overflow

Transferring a String array to Binary Tree

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related