sort a binary tree in javascript

To sort a binary tree in JavaScript, we can perform an in-order traversal of the tree and store all the values in an array, then sort the array and rebuild the tree.

Here's the code to sort a binary tree in JavaScript:

index.tsx
// Node class
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Binary tree class
class BinaryTree {
  constructor() {
    this.root = null;
  }

  // add a node to the tree
  addNode(value) {
    const newNode = new Node(value);

    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let node = this.root;

    while (node) {
      if (value < node.value) {
        if (!node.left) {
          node.left = newNode;
          return this;
        }
        node = node.left;
      } else {
        if (!node.right) {
          node.right = newNode;
          return this;
        }
        node = node.right;
      }
    }
  }

  // get nodes in in-order traversal
  inOrderTraversal() {
    const result = [];

    const traverse = (node) => {
      if (node.left) traverse(node.left);
      result.push(node.value);
      if (node.right) traverse(node.right);
    };

    traverse(this.root);

    return result;
  }

  // sort binary tree
  sort() {
    const nodes = this.inOrderTraversal();

    this.root = null;

    const rebuild = (list) => {
      if (!list.length) return null;

      const mid = Math.floor(list.length / 2);

      const node = new Node(list[mid]);

      node.left = rebuild(list.slice(0, mid));
      node.right = rebuild(list.slice(mid + 1));

      return node;
    };

    this.root = rebuild(nodes);
  }
}
1431 chars
81 lines

To use this code, you can create a new binary tree instance, add nodes to the tree, and then call the sort() method to sort the tree:

index.tsx
const tree = new BinaryTree();

tree.addNode(5);
tree.addNode(2);
tree.addNode(7);
tree.addNode(1);
tree.addNode(6);

console.log(tree.inOrderTraversal()); // output: [1, 2, 5, 6, 7]

tree.sort();

console.log(tree.inOrderTraversal()); // output: [1, 2, 5, 6, 7]
263 chars
14 lines

gistlibby LogSnag