Tree Sort

function treeSort(arr, stats) {
  const n = arr.length;
  function makeNode(val) {
    return {
      val: val,
      left: null,
      right: null
    };
  }
  let root = null;
  for (let i = 0; i < n; i++) {
    compare(i, i);
    let node = makeNode(arr[i]);
    if (!root) {
      root = node;
      continue;
    }
    let curr = root;
    while (true) {
      if (arr[i] < curr.val) {
        if (!curr.left) {
          curr.left = node;
          break;
        }
        curr = curr.left;
      } else {
        if (!curr.right) {
          curr.right = node;
          break;
        }
        curr = curr.right;
      }
    }
  }
  let i = 0;
  function traverse(node) {
    if (!node) return;
    traverse(node.left);
    arr[i] = node.val;
    write(i, node.val);
    markSorted(i);
    i++;
    traverse(node.right);
  }
  traverse(root);
}

from types import SimpleNamespace

def treeSort(arr, stats):
    def makeNode(val):
        return SimpleNamespace(val=val, left=None, right=None)

    def traverse(node):
        nonlocal i
        if not node:
            return
        traverse(node.left)
        arr[i] = node.val
        write(i, node.val)
        markSorted(i)
        i += 1
        traverse(node.right)

    root = None
    for i in range(n):
        compare(i, i)
        node = makeNode(arr[i])
        if not root:
            root = node
            continue
        curr = root
        while True:
            if (arr[i] < curr.val):
                if not curr.left:
                    curr.left = node
                    break
                curr = curr.left
            else:
                if not curr.right:
                    curr.right = node
                    break
                curr = curr.right
    i = 0
    traverse(root)

#include <vector>
#include <algorithm>
int makeNode(int val);
void traverse(int node);

int makeNode(int val) {
    return {val: val, left: 0, right: 0};
}

void traverse(int node) {
    if(!node) {
        return;
    }
    traverse(node.left);
    arr[i] = node.val;
    write(i, node.val);
    markSorted(i);
    i++;
    traverse(node.right);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    int root = 0;
    for(int i=0; i<n; i++) {
        compare(i, i);
        int node = makeNode(arr[i]);
        if(!root) {
            root = node;
            continue;
        }
        int curr = root;
        while(1) {
            if((arr[i] < curr.val)) {
                if(!curr.left) {
                    curr.left = node;
                    break;
                }
                curr = curr.left;
            } else {
                if(!curr.right) {
                    curr.right = node;
                    break;
                }
                curr = curr.right;
            }
        }
    }
    int i = 0;
    traverse(root);
}

int makeNode(int val) {
    return {val: val, left: 0, right: 0};
}

void traverse(int node) {
    if(!node) {
        return;
    }
    traverse(node.left);
    arr[i] = node.val;
    write(i, node.val);
    markSorted(i);
    i++;
    traverse(node.right);
}

public void Sort(int[] arr, int n, dynamic stats) {
    int root = 0;
    for(int i=0; i<n; i++) {
        compare(i, i);
        int node = makeNode(arr[i]);
        if(!root) {
            root = node;
            continue;
        }
        int curr = root;
        while(true) {
            if((arr[i] < curr.val)) {
                if(!curr.left) {
                    curr.left = node;
                    break;
                }
                curr = curr.left;
            } else {
                if(!curr.right) {
                    curr.right = node;
                    break;
                }
                curr = curr.right;
            }
        }
    }
    int i = 0;
    traverse(root);
}

#include <stdio.h>
int makeNode(int val);
void traverse(int node);

int makeNode(int val) {
    return {val: val, left: 0, right: 0};
}

void traverse(int node) {
    if(!node) {
        return;
    }
    traverse(node.left);
    arr[i] = node.val;
    write(i, node.val);
    markSorted(i);
    i++;
    traverse(node.right);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    int root = 0;
    for(int i=0; i<n; i++) {
        compare(i, i);
        int node = makeNode(arr[i]);
        if(!root) {
            root = node;
            continue;
        }
        int curr = root;
        while(1) {
            if((arr[i] < curr.val)) {
                if(!curr.left) {
                    curr.left = node;
                    break;
                }
                curr = curr.left;
            } else {
                if(!curr.right) {
                    curr.right = node;
                    break;
                }
                curr = curr.right;
            }
        }
    }
    int i = 0;
    traverse(root);
}