package Assignment1;

public class DictBinTree implements Dict {
		Node root = null;
		int sizeOfTree = 0;
	public void dictbintree(){

	}
	@Override
	public void insert(int k) {
		sizeOfTree ++;
		Node z = new Node(k);
		Node y = null;
		Node x = root;

		while (x != null)
		{
			y = x;
			if (z.key < x.key)
			{
				x = x.left;
			} else
			{
				x = x.right;
			}
			z.parent = y;

		}
		if (y == null)
		{
			root = z;
		} else if (z.key < y.key)
		{
			y.left = z;
		} else
		{
			y.right = z;
		}
	}

@Override
public int[] orderedTraversal()
	{
		int[] orderedTree = new int[sizeOfTree];

		inorderTreeWalk(orderedTree, root, 0);

		return orderedTree;
	}

public int inorderTreeWalk(int[] orderedTree, Node startNode, int index)
	{
		Node x = startNode;
		int i = index;

		if (x != null)
		{
			i = inorderTreeWalk(orderedTree, x.left, i);
			orderedTree[i++] = x.key;
			i = inorderTreeWalk(orderedTree, x.right, i);
		}
		return i;
	}

@Override
public boolean search(int k)
	{
		Node x = root;

		while (x != null && k != x.key)
			if (k < x.key)
			{
				x = x.left;
			} else
			{
				x = x.right;
			}

		if( x == null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}

}