Binary Tree to Binary Search Tree Conversion

using System;

public class Node
{
    public int data;
    public Node left;
    public Node right;
}

public class GFG{
    
    // index pointer to pointer to the array index
    static int index;
 
 
    /* A helper function that stores inorder traversal of a tree rooted
    with node */
    static void storeInorder(Node node, int[] inorder)
    {
        // Base Case
        if (node == null)
            return;
 
        /* first store the left subtree */
        storeInorder(node.left, inorder);
 
        /* Copy the root's data */
        inorder[index] = node.data;
        index++; // increase index for next entry
 
        /* finally store the right subtree */
        storeInorder(node.right, inorder);
    }
 
    /* A helper function to count nodes in a Binary Tree */
    static int countNodes(Node root)
    {
        if (root == null)
            return 0;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
 
    /* A helper function that copies contents of arr[] to Binary Tree.
    This function basically does Inorder traversal of Binary Tree and
    one by one copy arr[] elements to Binary Tree nodes */
    static void arrayToBST(int[] arr, Node root)
    {
        // Base Case
        if (root == null)
            return;
 
        /* first update the left subtree */
        arrayToBST(arr, root.left);
 
        /* Now update root's data and increment index */
        root.data = arr[index];
        index++;
 
        /* finally update the right subtree */
        arrayToBST(arr, root.right);
    }
 
    // This function converts a given Binary Tree to BST
    static void binaryTreeToBST(Node root)
    {
        // base case: tree is empty
        if (root == null)
            return;
 
        /* Count the number of nodes in Binary Tree so that
        we know the size of temporary array to be created */
        int n = countNodes(root);
 
        // Create a temp array arr[] and store inorder traversal of tree in arr[]
        int[] arr = new int[n];
 
        storeInorder(root, arr);
 
        // Sort the array using library function for quick sort
        Array.Sort(arr);
         
         
        // Copy array elements back to Binary Tree
        index = 0;
        arrayToBST(arr, root);
    }
 
    /* Utility function to create a new Binary Tree node */
    static Node newNode(int data)
    {
        Node temp = new Node();
        temp.data = data;
        temp.left = null;
        temp.right = null;
        return temp;
    }
 
    /* Utility function to print inorder traversal of Binary Tree */
    static void printInorder(Node node)
    {
        if (node == null)
            return;
 
        /* first recur on left child */
        printInorder(node.left);
 
        /* then print the data of node */
        Console.Write(node.data + " ");
 
        /* now recur on right child */
        printInorder(node.right);
    }
 
    /* Driver function to test above functions */
    
    static public void Main (){
        
        Node root = null;
 
        /* Constructing tree given in the above figure
            10
            / \
            30 15
        /     \
        20     5 */
        root = newNode(10);
        root.left = newNode(30);
        root.right = newNode(15);
        root.left.left = newNode(20);
        root.right.right = newNode(5);
 
        // convert Binary Tree to BST
        binaryTreeToBST(root);
 
        Console.WriteLine("Following is Inorder Traversal of the converted BST: ");
        printInorder(root);
        
    }
}

// This code is contributed by avanitrachhadiya2155

using System;
using System.Collections.Generic;

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x)
    {
        val = x;
    }
}

public class GFG
{
    public static void Main(string[] args)
    {
        // Example binary tree
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(30);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(20);
        root.left.right = new TreeNode(5);

        // Convert binary tree to binary search tree
        TreeNode bst = ConvertToBST(root);

        Console.WriteLine("Following is Inorder Traversal of the converted BST:");
        PrintInorder(bst);
    }

    // Inorder traversal to store the nodes in a List
    public static void Inorder(TreeNode root, List<TreeNode> nodes)
    {
        if (root == null)
        {
            return;
        }
        Inorder(root.left, nodes);
        nodes.Add(root);
        Inorder(root.right, nodes);
    }

    // Function to construct a binary search tree from a sorted List
    public static TreeNode ConstructBST(List<TreeNode> nodes, int start, int end)
    {
        if (start > end)
        {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = nodes[mid];
        root.left = ConstructBST(nodes, start, mid - 1);
        root.right = ConstructBST(nodes, mid + 1, end);
        return root;
    }

    // Function to convert a binary tree to a binary search tree
    public static TreeNode ConvertToBST(TreeNode root)
    {
        List<TreeNode> nodes = new List<TreeNode>();
        Inorder(root, nodes);
        nodes.Sort((a, b) => a.val - b.val);
        return ConstructBST(nodes, 0, nodes.Count - 1);
    }

    // Function to print the inorder traversal of a binary tree
    public static void PrintInorder(TreeNode root)
    {
        if (root == null)
        {
            return;
        }
        PrintInorder(root.left);
        Console.Write(root.val + " ");
        PrintInorder(root.right);
    }
}

// by phasing17