[코딩인터뷰] 문제 4.5

	#region Question 4.5
	/*
	* 어떤 이진 트리가 이진 탐색 트리인지 판별하는 함수를 구현하라.
	*/
	/// <summary>
	/// <paramref name="root"/>가 이진 탐색 트리가 맞는지 판별한다.
	/// </summary>
	/// <param name="root">검사할 이진 트리</param>
	/// <returns><paramref name="root"/>가 이진 트리가 맞다면 <code>true</code>를 반환한다.</returns>
	public static bool Q5_CheckBST(BinaryTreeNode<IComparable> root)
	{
	return CheckBST(root, null, null);
	}
	private static bool CheckBST(BinaryTreeNode<IComparable> node, IComparable min, IComparable max)
	{
	if(node == null) { return true; }
	if( (min != null && node.Data.CompareTo(min) <= 0) || (max != null && node.Data.CompareTo(max) >= 0))
	{
	return false;
	}
	if(!CheckBST(node.Left, min, node.Data) || !CheckBST(node.Right, node.Data, max))
	{
	return false;
	}
	return true;
	}
	#endregion

view raw Code_Q4_5.cs hosted with ❤ by GitHub

	[TestMethod]
	public void Q4_5()
	{
	BinaryTreeNode<IComparable> root = new BinaryTreeNode<IComparable>(0)
	{
	Left = new BinaryTreeNode<IComparable>(1)
	{
	Left = new BinaryTreeNode<IComparable>(3),
	Right = new BinaryTreeNode<IComparable>(4),
	},
	Right = new BinaryTreeNode<IComparable>(2)
	};
	Assert.IsFalse(TreeGraph.Q5_CheckBST(root));
	root = new BinaryTreeNode<IComparable>(4)
	{
	Left = new BinaryTreeNode<IComparable>(2)
	{
	Left = new BinaryTreeNode<IComparable>(1),
	Right = new BinaryTreeNode<IComparable>(3)
	},
	Right = new BinaryTreeNode<IComparable>(6)
	{
	Left = new BinaryTreeNode<IComparable>(5),
	Right = new BinaryTreeNode<IComparable>(7)
	}
	};
	Assert.IsTrue(TreeGraph.Q5_CheckBST(root));
	}

view raw Test_Q4_5.cs hosted with ❤ by GitHub