Binary Search Tree

node v10.24.1
version: 1.0.0
endpointsharetweet
const BST = { createNode (value) { const node = { value, left: null, right: null } return node }, create (...values) { const first = values.shift() const tree = BST.createNode(first) const insertNode = (value, node) => { let current = node if (value < current.value) { if (current.left) { insertNode(value, current.left) } else { current.left = BST.createNode(value) } } else { if (current.right) { insertNode(value, current.right) } else { current.right = BST.createNode(value) } } } const walkPreOrder = (root, visitor) => { if (!root) { return } visitor(root) if (root.left) { walkPreOrder(root.left, visitor) } if (root.right) { walkPreOrder(root.right, visitor) } } const walkInOrder = (root, visitor) => { if (!root) { return } if (root.left) { walkInOrder(root.left, visitor) } visitor(root) if (root.right) { walkInOrder(root.right, visitor) } } const walkPostOrder = (root, visitor) => { if (!root) { return } if (root.left) { walkPostOrder(root.left, visitor) } if (root.right) { walkPostOrder(root.right, visitor) } visitor(root) } const walkLevelOrder = (root, visitor) => { const q = [root] while (q.length) { const node = q.shift() if (node) { visitor(node) if (node.left) { q.push(node.left) } if (node.right) { q.push(node.right) } } } } values.forEach(value => insertNode(value, tree)) return { root: tree, // Depth-First-Search - DFS preOrder: visitor => walkPreOrder(tree, visitor), inOrder: visitor => walkInOrder(tree, visitor), postOrder: visitor => walkPostOrder(tree, visitor), // Breadth-First-Search - BFS levelOrder: visitor => walkLevelOrder(tree, visitor) } } } const values = [8, 3, 1, 6, 4, 7, 10, 14, 13] const { root, // preOrder: walk, // inOrder: walk, postOrder: walk, // levelOrder: walk } = BST.create(...values) // console.log(JSON.stringify(root, null, 2)) const out = [] walk(node => { out.push(node.value) }) console.log(out.join(' -> ')) // pre order // 8 -> 3 -> 1 -> 6 -> 4 -> 7 -> 10 -> 14 -> 13 // in order // 1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14 // post order // 1 -> 4 -> 7 -> 6 -> 3 -> 13 -> 14 -> 10 -> 8 // level order // 8 -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13 // use pre order for copying a tree // use in order for a sorted tree // use post order when deleting a tree // *level order is not typically used with BST but exists here for example
Loading…

no comments

    sign in to comment