Skip to content

Instantly share code, notes, and snippets.

@realamirhe
Created October 28, 2021 03:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save realamirhe/61424f60e46c00fdcc905838c1108171 to your computer and use it in GitHub Desktop.
Save realamirhe/61424f60e46c00fdcc905838c1108171 to your computer and use it in GitHub Desktop.
in-order BTree traversal in typescript with generators
// binary tree
interface INode {
left: INode | null;
value: number;
right: INode | null;
}
class BinaryTree {
public root: INode;
constructor(value: number) {
this.root = this.newTreeNode(value);
}
private newTreeNode(value: number): INode {
return { value, left: null, right: null };
}
insert(value: number, node = this.root): INode {
if (node === null) return this.newTreeNode(value);
if (value < node.value) {
node.left = this.insert(value, node.left);
} else {
node.right = this.insert(value, node.right);
}
return node;
}
*inOrderTraverse(node = this.root): IterableIterator<INode> {
if (node.left != null) yield* this.inOrderTraverse(node.left);
yield node;
if (node.right != null) yield* this.inOrderTraverse(node.right);
}
}
const tree = new BinaryTree(10);
tree.insert(5);
tree.insert(4);
tree.insert(6);
tree.insert(11);
console.log([...tree.inOrderTraverse()].map(node => node.value).join(', '));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment