CODEWITHSUNDEEP
javatree
Pournima Bedarkar
Pournima Bedarkar

Reputation: 392

Creating a tree accpting users input in BFS

I am quite confused how to maintain the top of tree while traversing through BFS. I am accepting input like this :

5 // total number of nodes in tree (root node will always be 1)
  // this number also tells the number of lines that'll be coming up
2 3 // left and right child of root, tree be like : 1
                                                   / \
                                                  2   3
4 5 // left and right child of 2 , tree             1
                                                   / \
                                                  2   3
                                                 / \
                                                4   5
-1 -1 // left and right child of 3 , that's null
-1 -1 // left and right child of 4
-1 -1 // left and right child of 5

This continues in above fashion, user inputs the left and right child in BFS. But I am unable to comprehend how do I achieve this.

What my take was : 

LinkedList<Node> list = new LinkedList<Node>
list.add(root); //initially push root
while(list.peek()){  //while there is node left in linked list
    curr = list.poll();
    curr.left = new Node(x) // x = whatever is the user input is (using nextInt)
                            // and if it's -1, i'll make left child null
    curr.right = new Node(x) // same goes for this one
    ll.add(curr);

}

In the end, I need the reference to the root node, I don't know how do I get it? And also, is there any better method how I could achieve this task

Upvotes: 0

Views: 1186

Answers (1)

Wayne Jo
Wayne Jo

Reputation: 203

I hope below code might help you.

"readTree" function is used to reading tree.

public static Node readTree(Scanner in) {
    Queue<Node> queue = new LinkedList<Node>();
    Node root = new Node(1);
    queue.add(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        int left = in.nextInt();
        int right = in.nextInt();
        if (-1 != left) {
            node.left = new Node(left);
            queue.add(node.left);
        }
        if (-1 != right) {
            node.right = new Node(right);
            queue.add(node.right);
        }
    }
    return root;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    in.nextInt(); // number of nodes is not used.
    Node result = readTree(in);
}

Upvotes: 1

Related Questions