28:null 29:["$","title",null,{"children":"Binary Search Trees | Claudio Esperança | Observable"}] 2e:T6b9,class BinarySearchTree extends BinaryTree { constructor (...args) { super(...args); } // Finds a subtree whose root node has the given key. // If not found, returns the tree where one such node would be inserted. find (key) { if (!this.node) return this; if (this.node.entry.key == key) return this; if (this.node.entry.key < key) return this.node.right.find(key); return this.node.left.find(key) } // Inserts the given entry. Raises an error on duplicate keys. insert (entry) { let t = this.find (entry.key); if (t.node) throw `This key already in tree: ${entry.key}`; t.node = new BinaryTreeNode (entry, new BinarySearchTree(), new BinarySearchTree()) return t } // Returns the lefmost leaf node of this tree, which must // be non-empty leftmost () { if (!this.node) throw "Tree has no nodes"; if (!this.node.left.node) return this; return this.node.left.leftmost(); } // Deletes the entry in the root of this tree delete() { if (!this.node) throw "Tree has no nodes"; if (!this.node.left.node) { this.node = this.node.right.node } else if (!this.node.right.node) { this.node = this.node.left.node } else { let l = this.node.right.leftmost(); this.node.entry = l.node.entry; l.delete() } } // Returns a shallow copy of this tree clone() { if (!this.node) return new BinarySearchTree(); return new BinarySearchTree (new BinaryTreeNode (this.node.entry, this.node.left.clone(), this.node.right.clone())) } }2f:[] 2c:{"id":"886030bd9b06edd1","slug":"binary-search-trees","title":"Binary Search Trees","thumbnail":"1d370edd145578c6564eff95d6f4c70aa455f36b33f4a0057c85b9e063102b88","access_level":"public","create_time":"$D2020-03-31T15:39:46.521Z","update_time":"$D2025-04-08T19:28:38.414Z","view_time":null,"first_public_time":"$D2020-03-31T20:36:17.762Z","has_unpublished_edits":null,"fork":{"id":"ddab8a15ee29c22b","slug":"trees","title":"Trees","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"stars":3,"starred":false,"owner":{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024"},"version":540,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}],"members":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":18,"collection":{"id":"25c80ce374eaa429","slug":"data-structures","title":"Data Structures","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"type":"notebook","body":{"title":"Binary Search Trees","cells":[{"id":0,"value":"md`# Binary Search Trees\n\nJavaScript implementations of binary search trees as mentioned in Lecture 4 of [David Mount's course on Data Structures (CMSC420)](https://www.cs.umd.edu/class/fall2019/cmsc420-0201/lectures.html)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"md`

\n## A generic Binary Tree`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"md`** Class modeling a binary tree object.**
\nIt can be a link to a null tree or point to a root node`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"class BinaryTree {\n constructor(node = null) {\n this.node = node;\n }\n *preorder() {\n if (this.node) {\n yield this;\n yield* this.node.left.preorder();\n yield* this.node.right.preorder();\n }\n }\n *inorder() {\n if (this.node) {\n yield* this.node.left.inorder();\n yield this;\n yield* this.node.right.inorder();\n }\n }\n *postorder() {\n if (this.node) {\n yield* this.node.left.postorder();\n yield* this.node.right.postorder();\n yield this;\n }\n }\n toString() {\n if (this.node) return this.node.toString();\n return \"-\";\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":375,"value":"md`** Class modeling a binary tree _node_ object.**`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":378,"value":"class BinaryTreeNode {\n constructor (entry,left,right) {\n [this.entry,this.left,this.right] = [entry,left,right]\n }\n toString() {\n if (this.entry instanceof String) return this.entry;\n return this.entry.toString()\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":380,"value":"md`** Helper function to create a binary tree.**
\nIf called with no arguments, creates a null tree, otherwise creates\na tree with a root node constructed from the args.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":384,"value":"function BT (...args) {\n if (args.length == 0) return new BinaryTree ()\n return new BinaryTree(new BinaryTreeNode(...args))\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":386,"value":"md`** A sample \\`BinaryTree\\` **`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":389,"value":"bt = BT(\"A\",BT(\"B\",BT(),BT()),BT(\"C\",BT(),BT()))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":401,"value":"draw(bt)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"md`** Arrays with inorder, preorder and postorder traversals of the tree **`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":199,"value":"[...bt.inorder()].map(tree => tree.node.entry)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":202,"value":"[...bt.preorder()].map(tree => tree.node.entry)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"[...bt.postorder()].map(tree => tree.node.entry)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":433,"value":"md`

\n## Binary Search Tree`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":434,"value":"md`** Class modeling a node entry**
\nAn entry is composed of a \\`key\\`, which is used in searches, and a \\`value\\`, a generic data item associated with that key.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":439,"value":"class Entry {\n constructor (key,value = null) {\n [this.key,this.value] = [key,value]\n }\n toString () {\n if (this.value) return `${this.key} (${this.value})`\n return `${this.key}`\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":443,"value":"md`** Class modeling a Binary Search Tree **
\nAssumes that each key is unique (no duplicates).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":442,"value":"$2e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":454,"value":"md`** Helper function to create a BST from an array **`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":453,"value":"function BST(entries) {\n let t = new BinarySearchTree();\n for (let [k,v] of entries) t.insert(new Entry(k,v))\n return t\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":459,"value":"md`** A sample BST **`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":462,"value":"t = BST([[9,\"A\"],[7,\"B\"],[8,\"C\"],[1,\"D\"],[4,\"E\"],[5,\"F\"],[11,\"X\"]])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":465,"value":"draw(t)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":497,"value":"md`** Inorder traversal of \\`t\\`**`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":476,"value":"[...t.inorder()].map(tree => tree.node.entry.toString())","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":500,"value":"md`** A clone of \\`t\\` with key 7 deleted **`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":479,"value":"q = {\n let q = t.clone();\n q.find(7).delete();\n return q;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":481,"value":"draw(q)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":206,"value":"md`

\n## GraphViz drawing code`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"graphViz = (tree) => {\n if (tree instanceof BinaryTree) {\n let result = `digraph{`;\n let count = 0;\n let traverse = (root) => {\n if (root.node) {\n if (root.node.left.node) {\n result += `< ${root.node.toString()} > -> < ${root.node.left.node.toString()} >;\\n`;\n traverse(root.node.left)\n }\n else {\n result += 'null'+(++count)+'[shape = none, label=\"\"];\\n';\n result += `< ${root.node.toString()} > -> ${'null'+count} [arrowhead=\"tee\"];\\n`;\n }\n if (root.node.right.node) {\n result += `< ${root.node.toString()} > -> < ${root.node.right.node.toString()} >;\\n`;\n traverse(root.node.right);\n }\n else {\n result += 'null'+(++count)+'[shape = none, label=\"\"];\\n';\n result += `< ${root.node.toString()} > -> ${'null'+count} [arrowhead=\"tee\"];\\n`;\n }\n }\n }\n traverse (tree)\n return result + \"}\"\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"draw = (tree) => dot`${graphViz(tree)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"dot = require(\"@observablehq/graphviz@0.2\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W2f","stdlib":"1","titling":"auto"}} 2d:"$2c:body"