import java.util.*;
import java.io.*;

public class BST{
    private class Node{
        int data;
        Node left, right;

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

    private Node root;
    private int sum = 0;
    private int p = 0;

    private void insert(int data){
        if(root == null){
            root = new Node(data);
            return;
        }
        Node current = root;
        Node parent = null;
        while(current != null){
            parent = current;
            if(data < current.data)
                current = current.left;
            else
                current = current.right;
        }
        if(data < parent.data)
            parent.left = new Node(data);
        else
            parent.right = new Node(data);
    }

    private void levelOrder(){
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node current = queue.poll();
            System.out.print(current.data+" ");
            if(current.left != null)
                queue.add(current.left);
            if(current.right != null)
                queue.add(current.right);
        }
        System.out.println();
    }

    private void printLevelByLevel(){
        Queue<Node> queueOne = new LinkedList<>();
        Queue<Node> queueTwo = new LinkedList<>();
        queueOne.add(root);
        while(!queueOne.isEmpty() || !queueTwo.isEmpty()){
            while(!queueOne.isEmpty()){
                Node current = queueOne.poll();
                System.out.print(current.data+" ");
                if(current.left != null)
                    queueTwo.add(current.left);
                if(current.right != null)
                    queueTwo.add(current.right);
            }
            System.out.println();
            while(!queueTwo.isEmpty()){
                Node current = queueTwo.poll();
                System.out.print(current.data+" ");
                if(current.left != null)
                    queueOne.add(current.left);
                if(current.right != null)
                    queueOne.add(current.right);
            }
            System.out.println();
        }
    }

    private void spiralOrder(){
        Stack<Node> stackOne = new Stack<>();
        Stack<Node> stackTwo = new Stack<>();
        stackOne.push(root);
        while(!stackOne.isEmpty() || !stackTwo.isEmpty()){
            while(!stackOne.isEmpty()){
                Node current = stackOne.pop();
                System.out.print(current.data+" ");
                if(current.left != null)
                    stackTwo.push(current.left);
                if(current.right != null)
                    stackTwo.push(current.right);
            }
            System.out.println();
            while(!stackTwo.isEmpty()){
                Node current = stackTwo.pop();
                System.out.print(current.data+" ");
                if(current.right != null)
                    stackOne.push(current.right);
                if(current.left != null)
                    stackOne.push(current.left);
            }
            System.out.println();
        }
    }

    private List<List<Integer>> getVOT(Node root){
        List<List<Integer>> list = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        LinkedList<Integer> hd = new LinkedList<>();
        queue.add(root);
        hd.add(0);
        int min = 0;
        int max = 0;
        while(!queue.isEmpty()){
            Node current = queue.poll();
            int l = hd.poll();
            min = Math.min(min, l); max = Math.max(max, l);
            if(map.containsKey(l))
                map.get(l).add(current.data);
            else{
                List<Integer> temp = new ArrayList<>();
                temp.add(current.data);
                map.put(l, temp);
            }
            if(current.left != null){
                queue.add(current.left);
                hd.add(l - 1);
            }
            if(current.right != null){
                queue.add(current.right);
                hd.add(l + 1);
            }
        }
        for(int i=min; i <= max; i++)
            if(map.containsKey(i))
                list.add(map.get(i));
        return list;
    }

    private List<List<Integer>> getLOT(Node root){
        List<List<Integer>> output = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        LinkedList<Integer> level = new LinkedList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        queue.add(root);
        level.add(0);
        int max = 0;
        while(!queue.isEmpty()){
            Node current = queue.poll();
            int l = level.poll();
            max = Integer.max(l, max);
            if(map.containsKey(l))
                map.get(l).add(current.data);
            else{
                List<Integer> temp = new ArrayList<>();
                temp.add(current.data);
                map.put(l, temp);
            }
            if(current.left != null){
                queue.add(current.left);
                level.add(l + 1);
            }
            if(current.right != null){
                queue.add(current.right);
                level.add(l + 1);
            }
        }
        for(int i=0; i<=max; i++)
            if(map.containsKey(i))
                output.add(map.get(i));
        return output;
    }

    private List<List<Integer>> getDOT(Node root){
        List<List<Integer>> output = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        LinkedList<Integer> dd = new LinkedList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        int max = 0;
        queue.add(root);
        dd.add(0);
        while(!queue.isEmpty()){
            Node current = queue.poll();
            int d = dd.poll();
            max = Math.max(d, max);
            if(map.containsKey(d))
                map.get(d).add(current.data);
            else{
                List<Integer> temp = new ArrayList<>();
                temp.add(current.data);
                map.put(d, temp);
            }
            if(current.left != null){
                queue.add(current.left);
                dd.add(d + 1);
            }
            if(current.right != null){
                queue.add(current.right);
                dd.add(d);
            }
        }
        for(int i=0; i<=max; i++)
            if(map.containsKey(i))
                output.add(map.get(i));
        return output;
    }

    private void printDiagonalOrderTraversal(){
        List<List<Integer>> output = getDOT(root);
        output.forEach(e->{
            e.forEach(t->System.out.print(t+" "));
            System.out.println();
        });
    }

    private void printLevelOrderTraversal(){
        List<List<Integer>> output = getLOT(root);
        output.forEach(e->{
            e.forEach(t->System.out.print(t+" "));
            System.out.println();
        });
    }


    private void printVerticalOrderTraversal(){
        List<List<Integer>> output = getVOT(root);
        output.forEach(e->{
            e.forEach(t->System.out.print(t+" "));
            System.out.println();
        });
    }

    private void printTopView(){
        List<List<Integer>> output = getVOT(root);
        output.forEach(e->System.out.print(e.get(0)+" "));
        System.out.println();
    }

    private void printBottomView(){
        List<List<Integer>> output = getVOT(root);
        output.forEach(e->System.out.print(e.get(e.size() - 1)+" "));
        System.out.println();
    }

    private void printLeftView(){
        List<List<Integer>> output = getLOT(root);
        output.forEach(e->System.out.print(e.get(0)+" "));
        System.out.println();
    }

    private void printRightView(){
        List<List<Integer>> output = getLOT(root);
        output.forEach(e->System.out.print(e.get(e.size() - 1)+" "));
        System.out.println();
    }

    private void greaterTree(Node root){
        if(root != null){
            greaterTree(root.right);
            sum += root.data;
            root.data = sum;
            greaterTree(root.left);
        }
    }

    private void makeTreeGreater(){
        greaterTree(root);
    }

    private Node lca(Node root, int a, int b){
        Node current = root;
        while(current != null){
            if(current.data > Math.max(a, b))
                current = current.left;
            if(current.data < Math.min(a, b))
                current = current.right;
            else
                break;
        }
        return current;
    }

    private int getLCA(int a, int b){
        return lca(root, a, b).data;
    }

    private boolean isLeaf(Node root){
        return root.left == null && root.right == null;
    }

    private boolean getPath(Node root, int sum, List<Integer> output){
        if(root == null) return false;
        if(isLeaf(root)){
            if(root.data == sum){
                output.add(root.data);
                return true;
            }
            else return false;
        }
        if(getPath(root.left, sum - root.data, output)){
            output.add(root.data);
            return true;
        }
        if(getPath(root.right, sum - root.data, output)){
            output.add(root.data);
            return true;
        }
        return false;
    }

    private List<Integer> getSumPath(int sum){
        List<Integer> output = new ArrayList<>();
        if(getPath(root, sum, output)){
            Collections.reverse(output);
            return output;
        }
        else
            return new ArrayList<>();
    }

    private Node getMax(Node root){
        Node current = root;
        while(current.right != null)
            current = current.right;
        return current;
    }

    private Node delete(Node root, int data){
        if(root == null) return root;
        if(data < root.data) root.left = delete(root.left, data);
        else if(data > root.data) root.right = delete(root.right, data);
        else{
            if(isLeaf(root)) root = null;
            else if(root.left == null) root = root.right;
            else if(root.right == null) root = root.left;
            else{
                Node temp = getMax(root.left);
                root.data = temp.data;
                root.left = delete(root.left, temp.data);
            }
        }
        return root;
    }

    private void delete(int data){
        root = delete(root, data);
    }

    private Node construct(int[] preorder, int data, int min, int max){
        int value = preorder[p];
        if(value > min && value < max){
            Node root = new Node(data);
            p += 1;
            if(p < preorder.length){
                root.left = construct(preorder, preorder[p], min, data);
                root.right = construct(preorder, preorder[p], data, max);
            }
            return root;
        }
        else
            return root;
    }

    private void construct(int[] preorder){
        root = construct(preorder, preorder[0], Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public static void main(String[] args){
        int[] a = {17, 9, 25, 5, 11, 20, 27, 4, 6, 10, 12, 19, 21, 26, 28};
        int[] b = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        BST bst = new BST();
        int[] preorder = {10, 5, 1, 7, 40, 50};
        bst.construct(preorder);
        bst.printLevelByLevel();
    }
}