next_highest.cs

using System;

public class Program
{
	public class TreeNode
	{
		public int Value;
		public TreeNode Left;
		public TreeNode Right;
		public TreeNode(int val)
		{
			Value = val;
		}
	}

	public class NextHighestFinder
	{
		public TreeNode Tree;
		public NextHighestFinder(TreeNode treeNode)
		{
			Tree = treeNode;
		}

		public int FindNextHighestOf(int val)
		{
			var root = Tree;
			return Find(root, Int32.MaxValue, val);
		}

		public int Find(TreeNode node, int nextHighest, int val)
		{
			if (node.Value < nextHighest && node.Value > val)
			{
				nextHighest = node.Value;
			}

			if (node.Value > val && node.Left != null)
			{
				node = node.Left;
				return Find(node, nextHighest, val);
			}
			else if (node.Value <= val && node.Right != null)
			{
				node = node.Right;
				return Find(node, nextHighest, val);
			}

			return nextHighest;
		}
	}

	public static void Main()
	{
		var root = new TreeNode(8);
		root.Left = new TreeNode(3);
		root.Left.Left = new TreeNode(1);
		root.Left.Right = new TreeNode(6);
		root.Left.Right.Left = new TreeNode(4);
		root.Left.Right.Right = new TreeNode(7);
		root.Right = new TreeNode(10);
		root.Right.Right = new TreeNode(14);
		root.Right.Right.Left = new TreeNode(13);
		Console.WriteLine("Case 1: 13 vs {0}", (new NextHighestFinder(root)).FindNextHighestOf(10));
		Console.WriteLine("Case 2: 7 vs {0}", (new NextHighestFinder(root)).FindNextHighestOf(6));
		Console.WriteLine("Case 3: 8 vs {0}", (new NextHighestFinder(root)).FindNextHighestOf(7));
		Console.WriteLine("Case 4: 3 vs {0}", (new NextHighestFinder(root)).FindNextHighestOf(1));
		Console.WriteLine("Case 5: 4 vs {0}", (new NextHighestFinder(root)).FindNextHighestOf(3));
	}
}