Tree Sort

function treeSort(arr) {
  class Node { constructor(v) { this.val=v; this.left=this.right=null; } }
  function insert(root, v) {
    if (!root) return new Node(v);
    if (v < root.val) root.left = insert(root.left, v);
    else root.right = insert(root.right, v);
    return root;
  }
  let root = null;
  for (const v of arr) root = insert(root, v);
  // In-order traversal fills sorted array
}

def tree_sort(arr):
    class Node:
        def __init__(self, v):
            self.val, self.left, self.right = v, None, None
    def insert(root, v):
        if not root: return Node(v)
        if v < root.val: root.left = insert(root.left, v)
        else: root.right = insert(root.right, v)
        return root
    root = None
    for v in arr: root = insert(root, v)
    # In-order traversal fills sorted array

void treeSort(vector<int>& arr) {
  multiset<int> bst(arr.begin(), arr.end());
  int idx = 0;
  for (int v : bst) arr[idx++] = v;
}

class Node { public int Val; public Node L, R; }
Node Insert(Node root, int v) {
  if (root == null)
    return new Node { Val = v };
  if (v < root.Val) root.L = Insert(root.L, v);
  else root.R = Insert(root.R, v);
  return root;
}
void InOrder(Node node, int[] outArr, ref int idx) {
  if (node == null) return;
  InOrder(node.L, outArr, ref idx);
  outArr[idx++] = node.Val;
  InOrder(node.R, outArr, ref idx);
}
void TreeSort(int[] arr) {
  Node root = null;
  foreach (int v in arr) root = Insert(root, v);
  int k = 0;
  InOrder(root, arr, ref k);
}

typedef struct Node { int val; struct Node *l, *r; } Node;
Node* insert(Node* root, int v) {
  if (!root) { root = malloc(sizeof(Node));
    root->val = v; root->l = root->r = NULL; return root; }
  if (v < root->val) root->l = insert(root->l, v);
  else root->r = insert(root->r, v);
  return root;
}
void inOrder(Node* root, int out[], int* idx) {
  if (!root) return;
  inOrder(root->l, out, idx);
  out[(*idx)++] = root->val;
  inOrder(root->r, out, idx);
}
void treeSort(int arr[], int n) {
  Node* root = NULL;
  for (int i = 0; i < n; i++) root = insert(root, arr[i]);
  int k = 0;
  inOrder(root, arr, &k);
}