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

namespace BinarySearchTreeSplitTree
{
    /// <summary>
    /// The algorith is written for my mock interview to test the candidate recursive solution.
    /// Leetcode 776: Split binary search tree
    /// </summary>
    class Program
    {
        internal class TreeNode
        {
            public int Value { get; set; }
            public TreeNode Left { get; set; }
            public TreeNode Right { get; set; }

            public TreeNode(int number)
            {
                Value = number;
            }
        }

        static void Main(string[] args)
        {
            RunTestcase();
        }

        public static void RunTestcase()
        {
            // work on root node
            var node20 = new TreeNode(20);

            // work on level 1
            var node9 = new TreeNode(9);
            var node25 = new TreeNode(25);

            // work on connection from root node to its children
            node20.Left = node9;
            node20.Right = node25;

            // work on level 2
            var node5 = new TreeNode(5);
            var node12 = new TreeNode(12);

            // work on connection from level 1's nodes to their children
            node9.Left = node5;
            node9.Right = node12;

            // work on level 3
            var node11 = new TreeNode(11);
            var node14 = new TreeNode(14);

            // work on connection from level 2's nodes to their children
            node12.Left = node11;
            node12.Right = node14;

            var successor1 = SplitTree(node20, 15);

            var successor2 = SplitTree(node20, 9);

            var successor3 = SplitTree(node20, 11);
        }

        /// <summary>
        /// Split binary search tree
        /// First tree with node value small and equal to the target value.
        /// Second tree with node value greater than the target value.
        /// </summary>
        /// <param name="root"></param>
        /// <param name="givenNode"></param>
        /// <returns></returns>
        public static TreeNode[] SplitTree(TreeNode root, int target)
        {
            if (root == null)
            {
                return new TreeNode[2];
            }

            var splitLeftSubTree = root.Value > target;

            if (splitLeftSubTree)
            {
                var childTrees = SplitTree(root.Left, target);

                var tmp = childTrees[1];
                childTrees[1] = root;
                childTrees[1].Left = tmp;

                return childTrees;
            }
            else
            {
                var childTrees =  SplitTree(root.Right, target);

                var tmp = childTrees[0];

                childTrees[0] = root;
                childTrees[0].Right = tmp;

                return childTrees;
            }
        }
    }
}