using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

         BinaryTree tree = new BinaryTree();

        Node root = null;

        root = tree.insert(root, 4);

        tree.insert(root, 2);

        tree.insert(root, 1);

        tree.insert(root, 3);

        tree.insert(root, 6);

        tree.insert(root, 5);

          // Function call

        Console.WriteLine("Minimum value of BST is "

                          + tree.minvalue(root));

        Console.WriteLine("Height of tree is "

                          + tree.maxDepth(root));

        //Console.Write("Finding K-th largest Node in BST : " + KthLargestUsingMorrisTraversal(root, 2).data);

    }

    //Write a function to find the node with minimum value in a Binary Search Tree.

    //This is quite simple. Just traverse the node from root to left recursively until left is NULL. 

    //The node whose left is NULL is the node with minimum value

    //Time Complexity: O(Height of the BST)

    //Auxiliary Space: O(1)

​

​

    // A binary tree node

    public class Node {

​

        public int data;

        public Node left, right;

​

        public Node(int d)

        {

            data = d;

            left = right = null;

        }

    }

​

    public class BinaryTree {

​

        public static Node head;

​

        /* Given a binary search tree and a number,

         inserts a new node with the given number in

         the correct place in the tree. Returns the new

         root pointer which the caller should then use

         (the standard trick to avoid using reference

         parameters). */

        public virtual Node insert(Node node, int data)

        {

​

            /* 1. If the tree is empty, return a new,

             single node */

            if (node == null) {

                return (new Node(data));

            }

            else {

​

                /* 2. Otherwise, recur down the tree */

                if (data <= node.data) {

                    node.left = insert(node.left, data);

                }

                else {

                    node.right = insert(node.right, data);

                }

​

                /* return the (unchanged) node pointer */

                return node;

            }

        }

​

        /* Given a non-empty binary search tree,

         return the minimum data value found in that

         tree. Note that the entire tree does not need

         to be searched. */

        public virtual int minvalue(Node node)

        {

            Node current = node;

​

            /* loop down to find the leftmost leaf */

            while (current.left != null) {

                current = current.left;

            }

            return (current.data);

        }

        /* Compute the "maxDepth" of a tree -- the number of

        nodes along the longest path from the root node

        down to the farthest leaf node.*/

        public int maxDepth(Node node)

        {

            if (node == null)

                return 0;

            else {

                /* compute the depth of each subtree */

                int lDepth = maxDepth(node.left);

                int rDepth = maxDepth(node.right);

​

                /* use the larger one */

                if (lDepth > rDepth)

                    return (lDepth + 1);

                else

                    return (rDepth + 1);

            }

        }

        // Function to find the height(depth) of the tree

        public int height()

        {

            // Initialising a variable to count the

            // height of tree

            int depth = 0;

​

            Queue<Node> q = new Queue<Node>();

​

            // Pushing first level element along with NULL

            q.Enqueue(head);

            q.Enqueue(null);

            while (q.Count != 0) {

                Node temp = q.Dequeue();

​

                // When NULL encountered, increment the value

                if (temp == null)

                    depth++;

​

                // If NULL  not encountered, keep moving

                if (temp != null) {

                    if (temp.left != null) {

                        q.Enqueue(temp.left);

                    }

                    if (temp.right != null) {

                        q.Enqueue(temp.right);

                    }

                }

​

                // If queue still have elements left,

                // push NULL again to the queue

                else if (q.Count != 0) {

                    q.Enqueue(null);

                }

            }

            return depth;

        }

        public static Node KthLargestUsingMorrisTraversal(Node root, int k)

        {

            Node curr = root;

            Node Klargest = null;

​

            // count variable to keep count of visited Nodes

            int count = 0;

​

            while (curr != null)

            {

                // if right child is NULL

                if (curr.right == null)

                {

​

                    // first increment count and check if count = k

                    if (++count == k)

                        Klargest = curr;

​

                    // otherwise move to the left child

                    curr = curr.left;

                }

​

                else

                {

​

                    // find inorder successor of current Node

                    Node succ = curr.right;

​

                    while (succ.left != null && succ.left != curr)

                        succ = succ.left;

​

                    if (succ.left == null)

                    {

​

                        // set left child of successor to the

                        // current Node

                        succ.left = curr;

​

                        // move current to its right

                        curr = curr.right;

                    }

​

                    // restoring the tree back to original binary

                    // search tree removing threaded links

                    else

                    {

​

                        succ.left = null;

​

                        if (++count == k)

                            Klargest = curr;

​

                        // move current to its left child

                        curr = curr.left;

                    }

                }

            }

            return Klargest;

        }

    }

    //Given a binary tree, the task is to find the height of the tree. 

    //Height of the tree is the number of edges in the tree from the root to the deepest node, Height of the empty tree is 0.

    //Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1. 

    //See below pseudo code and program for details.

    /**

    Example Tree

            1

        2       3

    4       5

    maxDepth(‘1’) = max(maxDepth(‘2’), maxDepth(‘3’)) + 1 = 2 + 1

    because recursively 

    maxDepth(‘2’) =  max (maxDepth(‘4’), maxDepth(‘5’)) + 1 = 1 + 1 and  (as height of both ‘4’ and ‘5’ are 1)

    maxDepth(‘3’) = 1

    Follow the below steps to Implement the idea:

​

    Recursively do a Depth-first search.

    If the tree is empty then return -1

    Otherwise, do the following

    Get the max depth of the left subtree recursively  i.e. call maxDepth( tree->left-subtree)

    Get the max depth of the right subtree recursively  i.e. call maxDepth( tree->right-subtree)

    Get the max of max depths of left and right subtrees and add 1 to it for the current node.

    max_depth = max(max dept of left subtree,  max depth of right subtree) + 1

    Return max_depth.

    Time Complexity: O(N) (Please see our post Tree Traversal for details)

    Auxiliary Space: O(N) due to recursive stack.

    **/

}