using System;

​

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        var input = new int[]{2, 3, 4, 7, 17, 19, 21, 35, 89};

        var root = CreateBSTFromSortedArray(input, 0, input.Length - 1);

        Console.WriteLine("Found Iterative without stack {0}", FindNodeIterative(root, 19).Value);

        Console.WriteLine("Found Recursive {0}", FindNodeRecursive(root, 19).Value);

    }

​

    public static Node FindNodeIterative(Node root, int target)

    {

        var node = root;

        while (node != null)

        {

            if (target > node.Value)

            {

                node = node.Right;

            }

            else if (target < node.Value)

            {

                node = node.Left;

            }

            else

            {

                return node;

            }

        }

​

        return null;

    }

​

    public static Node FindNodeRecursive(Node node, int target)

    {

        if (node == null)

        {

            return null;

        }

​

        Node result = null;

        if (target < node.Value)

        {

            result = FindNodeRecursive(node.Left, target);

        }

        else if (target > node.Value)

        {

            result = FindNodeRecursive(node.Right, target);

        }

        else

        {

            result = node;

        }

​

        return result;

    }

    public static Node CreateBSTFromSortedArray(int[] sourceArray, int start, int end){

        if(end < start){

            return null;

        }

        var median = (start + end) / 2;

        var node = new Node(sourceArray[median]);

        node.Left = CreateBSTFromSortedArray(sourceArray, start, median - 1);

        node.Right = CreateBSTFromSortedArray(sourceArray, median + 1, end);

        return node;

    }

​

    public class Node{

        public int Value {get; private set;}

        public Node Left  {get; set;}

        public Node Right  {get; set;}

        public Node(int nodeValue){

            Value = nodeValue;

        }

    }

}