import java.util.ArrayList;

public class Tree<T> {

	public void print(Node<T> root) {
		if (root == null)
			return;
		else {
			print(root.left);
			System.out.println(root.toString());
			print(root.right);
		}
	}

	public void saveTree(Node<T> root,ArrayList<T> list){
		if(root == null)
			return;
		saveTree(root.left, list);
		list.add(root.data);
		saveTree(root.right, list);
	}
	public Node<T> insert(Node<T> root, T data) {
		if (root == null) {
			root = new Node<>(data);
			return root;
		}
		if (root.compareTo(data) < 0) {
			root.right = insert(root.right, data);
			return root;
		}
		if (root.compareTo(data) > 0) {
			root.left = insert(root.left, data);
			return root;
		} else
			return null;
	}

	public Node<T> find(Node<T> root, T data) {
		if (data == null || root == null)
			return null;

		if (root.compareTo(data) == 0)
			return root;

		if (root.compareTo(data) < 0) {
			return find(root.right, data);
		}
		if (root.compareTo(data) > 0) {
			return find(root.left, data);

		} else
			return null;
	}

	public Node<T> findMax(Node<T> root) {
		if (root.right == null)
			return root;

		return findMax(root.right);

	}

	public Node<T> findMin(Node<T> root) {
		if (root.left == null)
			return root;

		return findMin(root.left);

	}

	public boolean isLeaf(Node<T> data) {
		return (data.left == null && data.right == null);
	}

	public boolean haveOnChild(Node<T> data) {
		return ((data.left == null && data.right != null) || (data.left != null && data.right == null));
	}

	public boolean haveTwoChild(Node<T> data) {
		return (data.left != null && data.right != null);
	}

	public Node<T> getParent(Node<T> root, T data) {
		if (root == null || data == null)
			return null;

		if (root.compareTo(data) < 0) {

			if (root.right.compareTo(data) == 0)
				return root;
			return getParent(root.right, data);
		} else if (root.compareTo(data) > 0) {
			if (root.left.compareTo(data) == 0)
				return root;
			return getParent(root.left, data);
		} else
			return root;

	}

	public Node<T> delete1(T value, Node<T> node) {
		if (node == null)
			return null;

		if (node.compareTo(value) > 0)
			node.left = delete1(value, node.left);

		else if (node.compareTo(value) < 0)
			node.right = delete1(value, node.right);

		else {
			if (isLeaf(node))
				return null;

			if (node.right == null)
				return node.left;

			if (node.left == null)
				return node.right;

			Node<T> pos = findMax(node.left);
			node.data = pos.data;

			node.left = delete1(pos.data, pos);

		}
		return node;
	}

	/*
	 * public boolean delete2(Node<T> root,T data){ Node<T> pos= find(root,
	 * data);
	 * 
	 * if(pos==null) return false;
	 * 
	 * Node<T> parent = getParent(root, pos.data);
	 * 
	 * if(isLeaf(pos)){
	 * 
	 * if(parent.right!=null){ parent.right=null; return true; }
	 * parent.left=null; return true; }
	 * 
	 * if(pos.right==null){
	 * 
	 * parent.left=pos.left;
	 * 
	 * return true; }
	 * 
	 * if(pos.left==null){
	 * 
	 * parent.right=pos.right;
	 * 
	 * return true; } Node<T> max = findMax(pos.left); pos.data=max.data; return
	 * delete2(root,max.data);
	 * 
	 * 
	 * }
	 */
	

	public void printGivenLevel(Node<T> root, int level) {
		if (root == null)
			return;
		if (level == 1)
			System.out.print(root.data + " ");
		else if (level > 1) {
			printGivenLevel(root.left, level - 1);
			printGivenLevel(root.right, level - 1);
		}
	}

	public int width(Node<T> root, int level) {
		if (root == null)
			return -1;
		if (level == 1)
			return 1;

		return width(root.left, level - 1) + width(root.right, level - 1);
	}

	public int countLeafs(Node<T> root) {

		if (root == null)
			return 0;

		if (isLeaf(root))
			return 1;
		else {
			return countLeafs(root.left) + countLeafs(root.right);
		}

	}

	public int[] saveInOrder(Node<Integer> root, int[] array, int data, int index) {
		if (root == null)
			array[index++] = data;

		if (root.left != null && root.right != null) {
			saveInOrder(root.left, array, root.left.data, index);
			data = root.data;
			// System.out.println();
			saveInOrder(root.right, array, root.right.data, index);
		}
		return array;

	}

	public int countNodes(Node<T> root) {
		if (root == null)
			return 0;

		return 1 + countNodes(root.left) + countNodes(root.right);

	}

	public int computeHiegth(Node<T> root) {
		if (root == null)
			return -1;
		else {
			return (Math.max(computeHiegth(root.left), computeHiegth(root.right))) + 1;
		}
	}
	
	public void printAllPaths(Node<Integer> root, int []array,int len){
		if(root != null){
			array[len++]= root.data;
			
			if(root.left == null && root.right==null)
				printData(array,len);
			else{
				printAllPaths(root.left, array, len);
				printAllPaths(root.right, array, len);
			}
		}
	}

	private void printData(int[] array, int len) {
		for (int i = 0; i < len; i++) {
			System.out.print(array[i] + " ");
		}		
		System.out.println();
	}

	
}
