public class Node {
		Node left, right = null;
		String Binary = "";
		int bValue = -1;;
	}

	int sizeofstrings = 0;
	Node root = new Node();
	int size = 0;
	int TrieLength;
	int trackBit = 0;

	public boolean insert(BinaryTrie trie, String a) { //this is the insert function
		if (trie.lexiordered.contains(a)) {
			return false;
		} else {

			sizeofstrings++;
			insertTheString(trie.root, a);
			return true;
		}

	}

	public void insertTheString(Node root, String a) {

		if (size == 0) {
			TrieLength = a.length();
		} // if this is the first string to be added, set the length of strings to be the
			// length of the first string
		if (root.Binary.equals("") && size == 0) {

			root.Binary = a;
			size++;
		} // if this is the root of the trie and it's empty, then add the string
		else if (root.Binary.equals("") && root.bValue == 0) {// if it's empty and is a path

			char newString[] = a.toCharArray();
			if (newString[trackBit] == '0') {

				trackBit++;
				if (root.left == null) { // if the left node doesn't exist, then that means we can put the binary string
											// there
					Node newNode = new Node();
					root.left = newNode;
					root.left.Binary = a; // put the new string in the left node
					trackBit = 0; // trackBit goes to 0
					return;
				} else {
					insertTheString(root.left, a);

					return;
				}
			}
			if (newString[trackBit] == '1') {

				trackBit++;
				if (root.right == null) { // if the right node doesn't exist, then that means we can put the binary
					// string there
					Node newNode = new Node();
					root.right = newNode;
					root.right.Binary = a; // put the new string in the right node
					trackBit = 0;// trackBit goes to 0
					return;

				} else {
					insertTheString(root.right, a);
					return;

				}
			}

		} else if (!root.Binary.equals("") && root.bValue == -1) {// if the node has a string in it
			char newString[] = a.toCharArray(); // converting the string to be inserted to a char array
			char oldString[] = root.Binary.toCharArray(); // converting the string that's already in the node to an
															// array

			// this goes over the two strings and compares them
			if (newString[trackBit] == oldString[trackBit] && newString[trackBit] == '1') {
				Node newNode = new Node();
				root.right = newNode;
				root.right.Binary = root.Binary;
				root.Binary = "";
				root.bValue = 0;
				trackBit++;
				insertTheString(root.right, a);
				return;
			}
			if (newString[trackBit] == oldString[trackBit] && newString[trackBit] == '0') {

				Node newNode = new Node();
				root.left = newNode;
				root.left.Binary = root.Binary;
				root.Binary = "";
				root.bValue = 0;

				trackBit++;

				insertTheString(root.left, a);
				return;
			}
			if (newString[trackBit] != oldString[trackBit]) { // here happens insertion of strings
				if (newString[trackBit] == '0') {
					Node newNode = new Node();
					root.left = newNode;
					root.left.Binary = a;
					root.bValue = 0;// this marks the node that it's a path now, and cannot be given any strings

					Node newNode2 = new Node();
					root.right = newNode2;
					root.right.Binary = root.Binary;
					root.Binary = "";
					trackBit = 0;

					return;
				} else if (newString[trackBit] == '1') {

					Node newNode = new Node();
					root.right = newNode;
					root.right.Binary = a;// put the new string in the right node
					root.bValue = 0;// this marks the node that it's a path now, and cannot be given any strings
					Node newNode2 = new Node();
					root.left = newNode2;
					root.left.Binary = root.Binary;
					root.Binary = "";
					trackBit = 0;

					return;
				}

			}

		}
	}