using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarySearchTreeSuccessor_mockingInterview
{
    /// <summary>
    /// binary search tree successor
    /// June 28, 2017
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            var root = new Node(30);

            root.Left  = new Node(19);
            root.Left.Parent = root;

            root.Right = new Node(30);
            root.Right.Parent = root;

            root.Left.Left  = new Node(15);
            root.Left.Left.Parent = root.Left;

            root.Left.Right = new Node(22);
            root.Left.Right.Parent = root.Left;

            var node22 = root.Left.Right;
            node22.Left  = new Node(21);
            node22.Left.Parent = node22;

            node22.Right = new Node(24);
            node22.Right.Parent = node22;

            var testcase1 = FindInOrderSuccessor(root.Left.Left);
            Debug.Assert(testcase1.Value == 19);

            var testcase2 = FindInOrderSuccessor(root.Left);
            Debug.Assert(testcase2.Value == 21);

            var testcase3 = FindInOrderSuccessor(node22.Right);
            Debug.Assert(testcase3.Value == 30);
        }

        class Node
        {
            public int  Value  { get; set; }
            public Node Left   { get; set; }
            public Node Right  { get; set; }
            public Node Parent { get; set; }

            public Node(int v)
            {
                Value = v;
            }
        }

        // given 15, find 19
        // test case 2: given node 24
        // test case 3: given node 35
        // test case 4: given node 19
        // test case 5: given node 30
        // test case 6: given node 21
        // time complexity - BST O(logN) - O(N) - space - linked list O(N)
        static Node FindInOrderSuccessor(Node inputNode)
        {
            // your code goes here
            if (inputNode == null)
            {
                return null;
            }

            // assume that node at least has one child
            bool hasRightChild = inputNode.Right != null; // false, false

            if (hasRightChild)
            {
                return getMinimum(inputNode.Right); // ? node 22 , return node 21
            }

            // now we can assume that the node does not have right child
            // find parent node which is bigger than givenNode
            var givenValue = inputNode.Value; // 15, 24, 35
            var iterate = inputNode;
            while (iterate.Parent != null && iterate.Parent.Value < givenValue)  // 19 > 15, 22 < 24, 30 > 24
            {
                iterate = iterate.Parent; // node 22, node 19
            }

            return iterate.Parent;
        }

        /// <summary>
        ///
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        private static Node getMinimum(Node root)
        {
            var minimum = root; // node 22
            while (minimum.Left != null)
            {
                minimum = minimum.Left; // node 21
            }

            return minimum; // return node 21
        }
    }
}