# Binary Tree to Binary Search Tree Conversion

Given a Binary Tree, convert it to a Binary Search Tree. The conversion must be done in such a way that keeps the original structure of Binary Tree.

Examples.

```
Example 1
Input:
          10
         /  \
        2    7
       / \
      8   4
Output:
          8
         /  \
        4    10
       / \
      2   7


Example 2
Input:
          10
         /  \
        30   15
       /      \
      20       5
Output:
          15
         /  \
       10    20
       /      \
      5        30
```

```java
class Solution {
    public void convertToBST(Node node) {
        LinkedList<Integer> list = new LinkedList<>();
        traverseToFillList(node, list);
        Collections.sort(list);
        traverseToFillFromList(node, list, 0, list.size() - 1);
    }

    public void traverseToFillList(Node node, LinkedList<Integer> list) {
        if (node == null)
            return;

        list.add(node.data);
        traverseToFillList(node.left, list);
        traverseToFillList(node.right, list);
    }

    public int numberOfNodes(Node node) {
        if (node == null)
            return 0;
        return 1 + numberOfNodes(node.left) + numberOfNodes(node.right);
    }

    public void traverseToFillFromList(Node node, LinkedList<Integer> list, int start, int end) {
        if (node == null)
            return;

        int l = numberOfNodes(node.left);
        node.data = list.get(start + l);

        traverseToFillFromList(node.left, list, start, start + l - 1);
        traverseToFillFromList(node.right, list, start + l + 1, end);
    }
}
```
