package algoexpert.medium;
import java.util.*;

/*
PROBLEM:
Implement Breadth First Search

-> time : O(v+e) | space : O(v)
*/

public class BFS
{
    static class Node
    {
        String name;
        ArrayList<Node> children = new ArrayList<Node>();

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

        // time : O(v+e) | space : O(v)
        public ArrayList<String> breadthFirstSearch(ArrayList<String> array)
        {
            Queue<Node> queue = new LinkedList<Node>();
            queue.add(this);

            while(queue.size() > 0)
            {
                Node current = queue.remove();
                array.add(current.name);

                for(int i = 0; i < current.children.size(); i++)
                { queue.add(current.children.get(i)); }
            }
            return array;
        }

        public Node addChild(String name)
        {
            Node child = new Node(name);
            children.add(child);
            return this;
        }
    }
}