Binary Search Tree: Test spec is unsuited for static typing

[peerreynders]

In particular:

https://github.com/exercism/typescript/blob/1af726c440639e59c5ac2c84881d3d654be2b22e/exercises/binary-search-tree/binary-search-tree.test.ts#L48-L53

The use of method chaining forces TypeScript to demand a return type of BinarySearchTree on both the left and right - which is nonsense as it is perfectly normal for there to be no BinarySearchTree on either the left or right or both - the correct type should be BinarySearchTree | undefined.

The example implementation sidesteps the issue by using the non-null assertion operator:

https://github.com/exercism/typescript/blob/1af726c440639e59c5ac2c84881d3d654be2b22e/exercises/binary-search-tree/binary-search-tree.example.ts#L30-L36

which in this context is inappropriate because it is entirely reasonable in this section of code for this._left_ or this._right_to be undefined.

Now perhaps the test could be salvaged by using the optional chaining operator.

But I think the core of the problem is that a binary search tree is usually used as an internal structure - so left and right would never be publicly exposed anyway.

So as a compromise it may make sense to have an export method that exports a simplified representation of the internal structure for testing purposes (so for the purpose of this exercise we are testing the implementation - not just the publicly exposed interface).

Then the test spec could look something like this:

// https://github.com/exercism/problem-specifications/blob/master/exercises/binary-search-tree/canonical-data.json

import BinarySearchTree from './binary-search-tree';

describe('BinarySearchTree', () => {
  it('should retain data', () => {
    const bst = new BinarySearchTree();
    bst.insert(4);
    expect(bst.export()).toEqual([undefined, 4, undefined]);
  });

  describe('insert data at proper node', () => {
    it('smaller number at left node', () => {
      const four = new BinarySearchTree([4, 2]);

      expect(four.export()).toEqual([2, 4, undefined]);
    });

    it('should insert the same number to the left', () => {
      const four = new BinarySearchTree([4, 4]);

      expect(four.export()).toEqual([4, 4, undefined]);
    });

    it('should insert a greater number to the right', () => {
      const four = new BinarySearchTree([4, 5]);

      expect(four.export()).toEqual([undefined, 4, 5]);
    });

    it('should deal with a complex tree', () => {
      const four = new BinarySearchTree([4, 2, 6, 1, 3, 7, 5]);

      expect(four.export()).toEqual([[1, 2, 3], 4, [5, 6, 7]]);
    });
  });

  describe('can sort data', () => {
    it('can sort single number', () => {
      expect(Array.from(new BinarySearchTree([2]))).toEqual([2]);
    });

    it('can sort if second number is smaller than first', () => {
      expect(Array.from(new BinarySearchTree([2, 1]))).toEqual([1, 2]);
    });

    it('can sort if second number is same as first"', () => {
      expect(Array.from(new BinarySearchTree([2, 2]))).toEqual([2, 2]);
    });

    it('can sort if second number is greater than first"', () => {
      expect(Array.from(new BinarySearchTree([2, 3]))).toEqual([2, 3]);
    });

    it('can sort complex tree', () => {
      expect(Array.from(new BinarySearchTree([2, 1, 3, 6, 7, 5]))).toEqual([
        1,
        2,
        3,
        5,
        6,
        7,
      ]);
    });
  });
});

with an example implementation like

```typescript // https://github.com/exercism/typescript/blob/master/exercises/binary-search-tree/README.md enum NodeKind { Empty, Node, } type NodeEmpty = { kind: NodeKind.Empty }; type NodeData = { kind: NodeKind.Node; data: number; left: Node; right: Node; }; type Node = NodeEmpty | NodeData; const NODE_EMPTY = { kind: NodeKind.Empty } as const; const newNodeData: (d: number) => Node = (data) => ({ kind: NodeKind.Node, data, left: NODE_EMPTY, right: NODE_EMPTY, }); function insert(node: NodeData, data: number): void { if (data <= node.data) { if (node.left.kind === NodeKind.Node) insert(node.left, data); else node.left = newNodeData(data); return; } if (node.right.kind === NodeKind.Node) insert(node.right, data); else node.right = newNodeData(data); } function* makeIterator(tree: Node): Generator { const stack: NodeData[] = []; let node: NodeData | undefined = tree.kind === NodeKind.Node ? tree : undefined; while (node || stack.length > 0) { while (node) { stack.push(node); node = node.left.kind === NodeKind.Node ? node.left : undefined; } const current = stack.pop()!; node = current.right.kind === NodeKind.Node ? current.right : undefined; yield current.data; } return; } type ExportEmpty = []; type ExportSubTree = ExportNode | number | undefined; type ExportNode = [ExportSubTree, number, ExportSubTree]; type ExportTree = ExportEmpty | ExportNode; const exportLeft: (n: NodeData) => ExportSubTree = (node) => node.left.kind === NodeKind.Node ? exportHelper(node.left) : undefined; const exportRight: (n: NodeData) => ExportSubTree = (node) => node.right.kind === NodeKind.Node ? exportHelper(node.right) : undefined; function exportHelper(node: NodeData): ExportSubTree { const left = exportLeft(node); const right = exportRight(node); return left || right ? [left, node.data, right] : node.data; } function exportTree(root: Node): ExportTree { switch (root.kind) { case NodeKind.Node: return [exportLeft(root), root.data, exportRight(root)]; default: return []; } } class BinarySearchTree { #tree: Node = NODE_EMPTY; constructor(values?: Iterable) { // Note: Due to coercion `values != null` // fails for both `null` and `undefined` if (values != null && typeof values[Symbol.iterator] === 'function') for (const v of values) this.insert(v); } insert(data: number): void { const tree = this.#tree; if (tree.kind === NodeKind.Node) insert(tree, data); else this.#tree = newNodeData(data); } [Symbol.iterator](): Iterator { return makeIterator(this.#tree); } export(): ExportTree { return exportTree(this.#tree); } } export default BinarySearchTree; // https://www.typescriptlang.org/docs/handbook/typescript-in-5-minutes-func.html#discriminated-unions ```

Also note that I replaced the former each method with an implementation of the standardized iterable protocol on the BinarySearchTree class.

[SleeplessByte]

I've mentioned before (on slack) that what you're doing now was one of my future goals. These exercises were ported when TS was waaaay younger and the porters were less experienced. So some of this is legacy, and some of it is just flat out wrong.

That said.

Now perhaps the test could be salvaged by using the optional chaining operator.

I think it should use the non-null assertion operator in the tests, to match the intent (e.g. returning undefined! from the left function right now would behave the same as left! in the tests.

But I think the core of the problem is that a binary search tree is usually used as an internal structure - so left and right would never be publicly exposed anyway.

Meh. It depends™. I agree that sometimes this is true, and sometimes it is not. There are plenty of libraries where left and right are exposed and meant to be public and publicly accessed.

the correct type should be BinarySearchTree | undefined.

💯 % agreed. This is the change I'd accept without comment.

The example implementation sidesteps the issue by using the non-null assertion operator:

This is just bad design. It should not have done this. I like your new implementation way better.

So as a compromise it may make sense to have an export method that exports a simplified representation of the internal structure for testing purposes (so for the purpose of this exercise we are testing the implementation - not just the publicly exposed interface)

You know how I love testing outcome and not implementation. I'm 50/50 on this. I like what you're proposing, but I want to ask a few other tracks their opinion.

If willing, could you do a PR that changes the return type, but not hide left and right for now (and change the example to be nice and correct), and then we can discuss removing left and right from the public API later?