2c:null 2d:["$","title",null,{"children":"Binary Search Trees: Find | T.J. Jankun-Kelly | Observable"}] 32:Te2d,{ const view = html`

` yield view; // The tree const tree = {value: 5, left: {value: 4, left: {value: 2, left: null, right: {value: 3, left: null, right: null}}, right: null}, right: {value: 7, left: {value: 6, left: null, right: null}, right: {value: 8, left: null, right: null}}}; // Generate animation steps let steps = []; let node = tree; while(node !== null && !isNaN(value)) { steps.push([node.value, 'lavender']); if(value == node.value) { steps.push([node.value, 'palegreen']); node = null; } else if(value < node.value && node.left !== null) { node = node.left; } else if(value > node.value && node.right !== null) { node = node.right; } else { steps.push([node.value, 'salmon']); node = null; } } // Walk through steps, inserting a walk over edge every other step let tree_view = d3.select(view); let step = 0; await Promises.delay(1500); while(step < steps.length) { tree_view.select('#n' + steps[step][0] + ">circle") .attr("fill", steps[step][1]) .attr("stroke-width", 3); if(step > 0) tree_view.select('#e' + steps[step-1][0] + steps[step][0]) .attr("stroke-width", 3); yield Promises.delay(1500, view); ++step; } }33:[] 30:{"id":"2c2774b43ab7ecc5","slug":"binary-search-trees-find","title":"Binary Search Trees: Find","thumbnail":"5ae8e3a7d29fe62575ce3b40cd6912623b52ffd18425be827a02ceee0ee42063","access_level":"public","create_time":"$D2020-06-29T18:27:27.529Z","update_time":"$D2020-08-29T15:51:44.575Z","view_time":null,"first_public_time":"$D2020-06-29T23:03:19.252Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":"starter_2024"},"version":179,"publish_version":179,"role":null,"authored":false,"authors":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null}],"members":[{"type":"individual","id":"e83a97795d4ad3a2","login":"infowantstobeseen","name":"T.J. Jankun-Kelly","avatar_url":"https://avatars-next.observableusercontent.com/df9d7f817f9ad92a763b56ee2e891ca0716a6c2f6c398811547f89f0448fa181","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":{"id":"e60edadcf2ad6765","slug":"data-structures","title":"Data Structures","owner":{"id":"57cbc1498c70b426","login":"infowantstobeseen","name":"T.J. Jankun-Kelly"}},"type":"notebook","body":{"titling":"auto","title":"Binary Search Trees: Find","cells":[{"id":0,"value":"md`# Binary Search Trees: Find\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"viewof value = number({placeholder: \"A whole number\", title: \"Search for\", submit: \"Find\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"md`Binary search trees (BSTs) are ordered so that items less than a node's value are to the left (when displayed in a [classic Reingold-Tilford](https://reingold.co/tidier-drawings.pdf \"'Tidier Drawing of Trees,' Reingold and Tilford, IEEE Trans. Soft. Eng, SE-7(2)\") like arrangement) and those greater are to the right (values are usually unique in a BST, though modifications exist). Searching the tree can then be expressed via a recursive algorithm:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"function find(root, value)\n{\n // root of (sub)tree is empty, nothing will be found\n if(root === null)\n return false;\n // Check to see if value found\n else if(root.value === value)\n return true;\n // Value not found; check left or right subtree\n else if(value < root.value)\n return find(root.left, value);\n else\n return find(root.right, value);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"md`Starting at the root of the tree, we continually check to see if the node's value is equal to a search term. If it is, we return a successful search; otherwise, we recurse to the left or right tree as appropriate. The runtime is bounded by the longest branch of the tree (anywhere between ${tex`n`} and ${tex`\\operatorname{lg} n`}, where ${tex`n`} is the number of nodes).\n\nThough tree algorithms are naturally recursive, search can use iteration if the tree's depth is exessive compared to stack space. This is left as an exercise to the reader.\n\nYou can see BST search in action via the demonstration above.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"import {number} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":130,"value":"d3 = require(\"d3-selection@1.4\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"ewidth = Math.min(width, 640)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1"}} 31:"$30:body"