How i can convert this input String to a BST(Binary-search-tree)-JAVA?

Question

I have to return true or false if an input String is a valid or not valid BST(Binary Search Tree).

The problem is that i have in input an atypical string with this "pattern" : ( ROOT (LEFT , RIGHT ) ); there is a space between every element, ROOT is the central node, LEFT the left one and RIGHT the right one. If a node is null is encoded like "-",a leaf is encoded with the numeric value, if a node have some child is encode in this way: For example B have two child (D at left,E at right) so ( A ( B ( D , E ) , C ) )

I have tried to split the string in an array of String but i have no idea how to populate the tree and at the same time check if it is a BST.How i can populate the tree with this String?

I would try with this algorithm:

//How i split the String

 String[] albero = b.readLine().split("\\,|\\(|\\)|\\-");

//How i would check if is a BST

public class IsBST {

    public boolean isBST(Node root){
        return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean isBST(Node root, int min, int max){
        if(root == null){
            return true;
        }
        if(root.data <= min || root.data > max){
            return false;
        }
        return isBST(root.left, min, root.data) && isBST(root.right, root.data, max);
    }

Example:

INPUT 1: ( 100 ( 19 ( 17 ( 2 , 7 ) , 3 ) , 36 ( 25 , 1 ) ) )

OUTPUT 1: false

INPUT 2: ( 8 ( 3 ( 1 , 6 ( 4 , 7 ) ) , 10 ( - , 14 ( 13 , - ) ) ) )

OUTPUT 2: true

Answer 1

To populate the BST you would take an element from the split up string (which one does not matter, it's probably easiest to make it the first element) and add it to an empty (newly created) BST and make the left and right sub-tree equal to '-'. You then can make an add function that have a base case when the root is '-' and puts the element that needs to be inserted in the root and sets the left and right child of the tree to a node with '-'. The recursive step would be to call on the left sub-tree if it is less then, or the right sub-tree if it is greater then. For example:

public void add (Node root, Node nodeToAdd){
if (root=='-'){
root=nodeToAdd;
root.left= new Node('-');
root.right=new Node('-');
}
if else (nodeToAdd<root) add(root.left, nodeToAdd);
else add(root.right, nodeToAdd);
}

So this will add an element to a BST and keep the binary property since every node has 2 children (all the leaves are '-'). If you just run this algorithm through your whole string it should populate a BST. Note the syntax will vary, but the idea of the function above should be the same.

Answer 2

Here is my approach:

First, we split the string into an array of the format [int, (, int (or -), int (or -), ...]:

String[] arr = str.substring(1, str.length()-1)
                .replaceAll("[^0-9-,()]","")
                .split(",|(?<=\\()|(?=\\()|(?<=\\))|(?=\\))");

We use:

• .substring(1, str.length()-1) to remove the parenthesis at the beginning and at the end of the string (since it is useless).
• .replaceAll("[^0-9-,()]","") to remove every characters except integers,-, ,, ( and ).
• .split(",|(?<=\\()|(?=\\()|(?<=\\))|(?=\\))") to split the string by ,, ) or ( but we keep the parentheses

Run the above splitting process with the input ( 8 ( 3 ( 1 , 6 ( 4 , 7 ) ) , 10 ( - , 14 ( 13 , - ) ) ) ) will yield:

String[] array = [8, (, 3, (, 1, 6, (, 4, 7, ), ), 10, (, -, 14, (, 13, -, ), ), )]

as desired.

---

Now, the rest is pretty straightforward. For every close parenthesis, a tree node can be constructed from: root, (, left, right, ). One way to achieve this is by using Stack: for every string in the array if the string is a number or character -, we construct a new node and push it the stack. Whenever there is a close parenthesis, the top 3 nodes on the stack are:

right
left
root

The full implementation:

public Node parseTree(String str){
    Stack<Node> nodes = new Stack<>();

    String[] arr = str.substring(1, str.length()-1).replaceAll("[^0-9-,()]","")
        .split(",|(?<=\\()|(?=\\()|(?<=\\))|(?=\\))");

    for (int i = 0; i < arr.length; i++){
        String c = arr[i];
        if (c.equals(")")){
            Node right = nodes.pop();
            Node left = nodes.pop();
            Node root = nodes.peek();
            root.left = left;
            root.right = right;
        }
        else if (c.equals("("))
            continue;
        else 
            nodes.push(c.equals("-") ? null : new Node(Integer.parseInt(c)));
    }

    return nodes.pop();
}

And Node is defined as:

class Node{
    Node left;
    Node right;
    int data;
    public Node(int data){
        this.data = data;
    }
}

Hope this helps.