BSTJun19

import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

class Node{
    private int value;
    private Node left;
    private Node right;
    
    
    public Node(int value){
        this.value= value;    
    }
    
    public int getValue(){
        return this.value;
    }
    
    public void setValue(int value){
        this.value=value;
    }
    
    public Node getRight(){
        return this.right;
    }
    
    public Node getLeft(){
        return this.left;
    }
    
    public void setRight(Node right){
        this.right= right;
    }
    
    public void setLeft(Node left){
        this.left= left;
    }
    
}

//BinarySearchTree implementation
class Main {
    
    private Node root;
    
    public Main(int rootValue){
        this.root= new Node(rootValue);
    }
    
    /*public void insertRecursive(int value){
        if (value == null){
            System.out.println("Cannot insert a null value");
            return;
        }
        /*if (this.root == null){
            this.root= new Node(value);
            return;
        }
        
        if (value < this.root.getValue()){
           insertRecursive(this.root.getLeft());
        }
        if (value > this.root.getValue()){
           insertRecursive(this.root.getRight());
        }
    }*/
    
    public void insertIterative(int value){
        Node currentNode = null;
        if (this.root ==null){
            this.root= new Node(value);
        }else {
            currentNode = this.root;
        }
        
        while (currentNode != null){
            if (value < currentNode.getValue()){
                if (currentNode.getLeft() != null){
                    currentNode = currentNode.getLeft();
                } else {
                    currentNode.setLeft(new Node(value));
                    return;
                }
                
            }
            if (value > currentNode.getValue()){
                if (currentNode.getRight() != null){
                    currentNode = currentNode.getRight();
                } else {
                    currentNode.setRight(new Node(value));
                    return;
                }
                
            }
        }    
    }
    
    public void lookupIterative(int value){
        Node currentNode = this.root;
        while (currentNode != null){
            if (value == currentNode.getValue()){
                System.out.println("Found a match for "+value);
                return;
            }
            if (value < currentNode.getValue()){
                if (currentNode.getLeft() != null){
                    currentNode = currentNode.getLeft();
                } else {
                    currentNode.setLeft(new Node(value));
                    return;
                }
                
            }
            if (value > currentNode.getValue()){
                if (currentNode.getRight() != null){
                    currentNode = currentNode.getRight();
                } else {
                    currentNode.setRight(new Node(value));
                    return;
                }
                
            }
        }    
    }
    
    public Node getRoot(){
        return this.root;
    }
    
    public String traverse(Node node){
        String tree = ""+node.getValue();
        
        tree += node.getLeft() != null ? " L:"+ traverse(node.getLeft()) : "";
        tree += node.getRight() != null ? " R:"+ traverse(node.getRight()) : "";
        
        return tree;
    }
    
    
    public ArrayList<Node> breathFirstSearchR(Queue<Node> queue, ArrayList<Node> nodesList){
        if (queue.isEmpty()){
            return nodesList;
        }
        
        Node currentNode = queue.poll();
        nodesList.add(currentNode);
        if (currentNode.getLeft() != null){
            queue.add(currentNode.getLeft());
        }
        if (currentNode.getRight() != null){
            queue.add(currentNode.getRight());
        }
        return breathFirstSearchR(queue, nodesList);
    }
    
    public static void main(String[] args) {
        Main bst= new Main(9);
        bst.insertIterative(4);
        bst.insertIterative(20);
        bst.insertIterative(1);
        bst.insertIterative(6);
        bst.insertIterative(15);
        bst.insertIterative(170);
        bst.lookupIterative(170);
        //System.out.println(bst.traverse(bst.getRoot()));
        
        Queue<Node> queue=new LinkedList<Node>();
        queue.add(bst.getRoot());
        ArrayList<Node> nodesList= bst.breathFirstSearchR(queue, new ArrayList<Node>());
        
        System.out.println("Nodes list: "+nodesList.size());
        for (Node node : nodesList){
            System.out.print(node.getValue() + " ");
        }
        
        
    }
}