import java.util.HashMap;
import java.util.TreeSet;

public class Tree implements Comparable<Tree>
{
    private Node root;

    public Tree()
    {
        root = null;

    }

    public Node getRoot()
    {
        return root;
    }

    public boolean isEmpty()
    {
        if (root == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public void insertData(int value)
    {
        root = new Node (value, null, null);
    }

    public void insertBranch (Node x, Node y)
    {
        if (y.getLeft() == null)
        {
            y.setLeft(x);
        }
        else
        {
            y.setRight(x);
        }
    }

    public int compareTo(Tree d)
    {
        if (this.getRoot().getData() < d.getRoot().getData())
        {
            return -1;
        }
        else
        {
            return 1;
        }
    }

    public boolean isLeaf (Node x)
    {
        if (x.getLeft() == null && x.getRight() == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public String codeGen (String input, Node x)
    {
        StringBuilder code = new StringBuilder();
        boolean flag = true;
        while (!isLeaf(x))
        {
            if (x.getLeft().getValue().contains(input))
            {
                x = x.getLeft();
                code.append("0");
            }
            else
            {
                x = x.getRight();
                code.append("1");
            }
        }
        return code.toString();
    }

    public String getCode (Node x, String y)
    {
        int count = 0;
        StringBuilder answer = new StringBuilder();
        while (count < y.length())
        {
            char c = y.charAt(count);
            if (c == '1')
            {
                x = x.getRight();
            }
            else
            {
                x = x.getLeft();
            }
            if (isLeaf(x))
            {
                answer.append(x.getValue());
                x = root;
            }
            count++;
        }
        return answer.toString();
    }

    public void outputTree( Node currentNode, int spaces)
    {
        if (currentNode == null)
        {
            return;
        }
        else 
        {
            outputTree(currentNode.getRight(), spaces + 5 );
            for ( int k = 1; k <= spaces; k++ )
            {
                System.out.print(" ");
            }
            System.out.println(currentNode.getData() + currentNode.getValue() + "     ");
            outputTree( currentNode.getLeft(), spaces + 5);
        }
    }

}