Created
September 15, 2017 21:58
-
-
Save fletcherist/3b39e9b83e82a138df02104cecbf810c to your computer and use it in GitHub Desktop.
BST Implementation is FP Style
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const merge = (...args) => Object.assign({}, ...args) | |
| const arrayFromObject = obj => Object.keys(obj).map(key => obj[key]) | |
| const getLastTreeIndex = tree => parseInt(Object.keys(tree).pop(), 10) | |
| const getNextTreeIndex = tree => getLastTreeIndex(tree) + 1 | |
| const getNodeParentIndex = (tree, {value}) => { | |
| let currentNode = tree[0] | |
| let currentIndex = 0 | |
| while (currentNode) { | |
| if (value >= currentNode.value) { | |
| currentNode = tree[currentNode.right] | |
| if (!currentNode) return currentIndex | |
| currentIndex = currentNode.index | |
| } else { | |
| currentNode = tree[currentNode.left] | |
| if (!currentNode) return currentIndex | |
| currentIndex = currentNode.index | |
| } | |
| } | |
| return null | |
| } | |
| const connectParentWithChild = (parent, childIndex, side) => | |
| merge(parent, {[side]: childIndex}) | |
| const getRelationshipBetweenChildAndParent = (parent, child) => | |
| child.value >= parent.value ? 'right' : 'left' | |
| const appendToTreeIndex = (tree, node) => { | |
| return merge( | |
| tree, | |
| {[getNextTreeIndex(tree)]: merge( | |
| node, | |
| {index: getNextTreeIndex(tree)} | |
| )}, | |
| {[getNodeParentIndex(tree, node)]: connectParentWithChild( | |
| tree[getNodeParentIndex(tree, node)], | |
| getNextTreeIndex(tree), | |
| getRelationshipBetweenChildAndParent( | |
| tree[getNodeParentIndex(tree, node)], | |
| node | |
| ) | |
| )} | |
| ) | |
| } | |
| const createNode = (value, index = 0) => ({ | |
| left: null, | |
| right: null, | |
| index, | |
| value | |
| }) | |
| const createInitialTree = initialValue => ({0: createNode(initialValue)}) | |
| const createBST = (initialValue, integers) => | |
| integers.reduce((bst, integer) => appendToTreeIndex(bst, createNode(integer)), | |
| createInitialTree(initialValue)) | |
| const wrapChildrenIntoParent = (parent, tree) => merge( | |
| parent, | |
| {left: tree[parent.left]}, | |
| {right: tree[parent.right]} | |
| ) | |
| const generateRandomArray = (count) => { | |
| const array = [] | |
| for (let i = 0; i < count; i++) { | |
| array.push(Math.floor(Math.random() * 100)) | |
| } | |
| return array | |
| } | |
| const bst = createBST(42, generateRandomArray(5)) | |
| console.log(bst) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment