using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
 
namespace Interview
{
public class BinaryTree
{
	public TreeNode root;
 
	public BinaryTree()
	{
		root = null;
	}
 
	public void print()
	{
		if (root == null)
			Console.WriteLine("Empty Tree");
		else
			printTree(root);
		Console.WriteLine();
	}
	private void printTree(TreeNode n)
	{
		if (n != null)
		{
			printTree(n.left);
			Console.Write(n.data + " ");
			printTree(n.right);
		}
	}
 
	public void insert(int x)
	{
		root = insert(root, x);
	}
	private TreeNode insert(TreeNode TreeNode, int data)
	{
		if (TreeNode == null)
		{
			TreeNode = new TreeNode();
			TreeNode.data = data;
		}
		else
		{
			if (data <= TreeNode.data)
			{
				TreeNode.left = insert(TreeNode.left, data);
			}
			else
			{
				TreeNode.right = insert(TreeNode.right, data);
			}
		}
		return (TreeNode);
	}
 
	public int Size()
	{
		return (Size(root));
	}
	private int Size(TreeNode TreeNode)
	{
		if (TreeNode == null) return 0;
		else
		{
			return Size(TreeNode.left) + 1 + Size(TreeNode.right);
		}
	}
 
	public int MaxDepth()
	{
		return MaxDepth(root);
	}
	private int MaxDepth(TreeNode TreeNode)
	{
		if (TreeNode == null) return 0;
		int lDepth = MaxDepth(TreeNode.left);
		int rDepth = MaxDepth(TreeNode.right);
 
		return Math.Max(lDepth, rDepth) + 1;
	}
 
	public int MinValue()
	{
		return MinValue(root);
	}
	private int MinValue(TreeNode TreeNode)
	{
		if (TreeNode.left == null) return TreeNode.data;
		else return MinValue(TreeNode.left);
	}
 
	public bool HasPathSum(int sum)
	{
		return HasPathSum(root, sum);
	}
	private bool HasPathSum(TreeNode TreeNode, int sum)
	{
		if (TreeNode == null)
		{
			return (sum == 0);
		}
		else
		{
			int temp = sum - TreeNode.data;
			return HasPathSum(TreeNode.left, temp) || HasPathSum(TreeNode.right, temp);
		}
	}
 
	public void PrintPaths()
	{
		int[] path = new int[1000];
		PrintPaths(root, path, 0);
	}
	private void PrintPaths(TreeNode TreeNode, int[] path, int pathLen)
	{
		if (TreeNode == null) return;
		path[pathLen] = TreeNode.data;
		pathLen++;
		if (TreeNode.left == null && TreeNode.right == null)
		{
			PrintPaths(path, pathLen);
		}
		else
		{
			PrintPaths(TreeNode.left, path, pathLen);
			PrintPaths(TreeNode.right, path, pathLen);
		}
	}
	private void PrintPaths(int[] ints, int len)
	{
		for (int i = 0; i < len; i++)
		{
			Console.Write(ints[i] + " ");
		}
		Console.WriteLine();
	}
 
	public void mirror()
	{
		mirror(root);
	}
	private void mirror(TreeNode TreeNode)
	{
		if (TreeNode != null)
		{
			mirror(TreeNode.left);
			mirror(TreeNode.right);
 
			TreeNode temp = TreeNode.left;
			TreeNode.left = TreeNode.right;
			TreeNode.right = temp;
		}
	}
 
	public void DoubleTree()
	{
		DoubleTree(root);
	}
	public void DoubleTree(TreeNode TreeNode)
	{
		if (TreeNode == null) return;
		DoubleTree(TreeNode.left);
		DoubleTree(TreeNode.right);
 
		TreeNode temp = TreeNode.left;
		TreeNode newNode = new TreeNode();
		newNode.data = TreeNode.data;
		TreeNode.left = newNode;
		TreeNode.left.left = temp;
	}
 
	public bool IsSameTree(BinaryTree tree)
	{
		return IsSameTree(root, tree.root);
	}
	private bool IsSameTree(TreeNode t1, TreeNode t2)
	{
		if (t1 == null && t2 == null) return (true);
		else if (t1 != null && t2 != null)
		{
			return (
				t1.data == t2.data &&
				IsSameTree(t1.left, t2.left) &&
				IsSameTree(t1.right, t2.right)
				);
		}
		else return (false);
	}
 
	public void PrintTreeLevelByLevel()
	{
		PrintTreeLevelByLevel(root);
	}
	private void PrintTreeLevelByLevel(TreeNode root)
	{
		if (root == null) return;
		Queue q = new Queue();
		q.Enqueue(root);
		while (q.Count > 0)
		{
			TreeNode b = (TreeNode)q.Dequeue();
			Console.Write(b.data + " ");
			if (b.left != null)
				q.Enqueue(b.left);
			if (b.right != null)
				q.Enqueue(b.right);
		}
	}
 
	public bool IsBST()
	{
		return (IsBST(root, Int32.MinValue, Int32.MinValue));
	}
	private bool IsBST(TreeNode TreeNode, int min, int max)
	{
		if (TreeNode == null)
		{
			return (true);
		}
		else
		{
			bool leftOk = IsBST(TreeNode.left, min, TreeNode.data);
			if (!leftOk) return (false);
			bool rightOk = IsBST(TreeNode.right, TreeNode.data + 1, max);
			return (rightOk);
		}
	}
}
 
public class TreeNode
{
	private int _data;
	private TreeNode _left;
	private TreeNode _right;
 
	public int data
	{
		get
		{
			return this._data;
		}
		set
		{
			this._data = value;
		}
	}
	public TreeNode left
	{
		get
		{
			return this._left;
		}
		set
		{
			this._left = value;
		}
	}
	public TreeNode right
	{
		get
		{
			return this._right;
		}
		set
		{
			this._right = value;
		}
	}
}
 
}