{"_id":"@andy0130tw/binary-search-tree","_rev":"2-4880cee0076e7c0d66836c654af61d87","name":"@andy0130tw/binary-search-tree","dist-tags":{"latest":"5.3.2-fork.1"},"versions":{"5.3.2-fork.0":{"name":"@andy0130tw/binary-search-tree","version":"5.3.2-fork.0","keywords":["binary search tree","bst js","bst es6","binary search tree es6","binary search tree js","avl tree","avl tree es6","avl tree js","self balancing tree"],"author":{"name":"Eyas Ranjous","email":"eyas.ranjous@gmail.com"},"license":"MIT","_id":"@andy0130tw/binary-search-tree@5.3.2-fork.0","maintainers":[{"name":"andy0130tw","email":"andy0130tw@yahoo.com.tw"}],"homepage":"https://github.com/datastructures-js/binary-search-tree#readme","bugs":{"url":"https://github.com/datastructures-js/binary-search-tree/issues"},"dist":{"shasum":"40fe8781c96c0a93411031c26df5bf981c76ef2a","tarball":"https://registry.npmjs.org/@andy0130tw/binary-search-tree/-/binary-search-tree-5.3.2-fork.0.tgz","fileCount":14,"integrity":"sha512-VmLynZGMQRroG9Hw1c9KnLYjcfOnIjh9TgsTz7KirSEyfyADhgo0xwKG2AQRzEnb9epc18XL8Wd98VPTZStz7A==","signatures":[{"sig":"MEUCIEHDVDpeSde+KVC1sNE0Fq9NbuJA2Xw9zE9uM/5TFG1fAiEA8O0+VXi9UBE3hYrWM3tXwcjIm1n5zzQwHMFu7pPfQFo=","keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U"}],"unpackedSize":49016},"main":"index.js","types":"index.d.ts","gitHead":"8b0f7551bf5598c96e689236ace0d9e26930cd34","scripts":{"test":"grunt test"},"_npmUser":{"name":"andy0130tw","email":"andy0130tw@yahoo.com.tw"},"repository":{"url":"git+https://github.com/datastructures-js/binary-search-tree.git","type":"git"},"_npmVersion":"11.4.0","description":"binary search tree & avl tree (self balancing tree) implementation in javascript","directories":{},"_nodeVersion":"22.14.0","_hasShrinkwrap":false,"devDependencies":{"chai":"^4.2.0","grunt":"^1.0.4","mocha":"^6.2.2","eslint":"^6.7.2","istanbul":"^0.4.5","grunt-eslint":"^22.0.0","grunt-mocha-test":"^0.13.3","eslint-plugin-import":"^2.19.1","grunt-mocha-istanbul":"^5.0.2","eslint-config-airbnb-base":"^14.0.0"},"_npmOperationalInternal":{"tmp":"tmp/binary-search-tree_5.3.2-fork.0_1748181266700_0.2714626721280433","host":"s3://npm-registry-packages-npm-production"}},"5.3.2-fork.1":{"name":"@andy0130tw/binary-search-tree","version":"5.3.2-fork.1","description":"binary search tree & avl tree (self balancing tree) implementation in javascript","main":"index.js","types":"index.d.ts","scripts":{"test":"grunt test"},"repository":{"type":"git","url":"git+https://github.com/datastructures-js/binary-search-tree.git"},"keywords":["binary search tree","bst js","bst es6","binary search tree es6","binary search tree js","avl tree","avl tree es6","avl tree js","self balancing tree"],"author":{"name":"Eyas Ranjous","email":"eyas.ranjous@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/datastructures-js/binary-search-tree/issues"},"homepage":"https://github.com/datastructures-js/binary-search-tree#readme","devDependencies":{"chai":"^4.2.0","eslint":"^6.7.2","eslint-config-airbnb-base":"^14.0.0","eslint-plugin-import":"^2.19.1","grunt":"^1.0.4","grunt-eslint":"^22.0.0","grunt-mocha-istanbul":"^5.0.2","grunt-mocha-test":"^0.13.3","istanbul":"^0.4.5","mocha":"^6.2.2"},"_id":"@andy0130tw/binary-search-tree@5.3.2-fork.1","_integrity":"sha512-stmqZm6PBzNAQTxcSKVJLbkFv4J7SPtiFgiRhs//Z+3LHU4Fo0D4k5XD/ABQqFp2s0Sbsg5Cp8Kn1vtTxZPugQ==","_resolved":"/home/qbane/agda-project/binary-search-tree/andy0130tw-binary-search-tree-5.3.2-fork.1.tgz","_from":"file:andy0130tw-binary-search-tree-5.3.2-fork.1.tgz","_nodeVersion":"22.23.1","_npmVersion":"12.0.1","dist":{"integrity":"sha512-stmqZm6PBzNAQTxcSKVJLbkFv4J7SPtiFgiRhs//Z+3LHU4Fo0D4k5XD/ABQqFp2s0Sbsg5Cp8Kn1vtTxZPugQ==","shasum":"79af9d11665a6eafdf912d88cbc0ff48af82dd42","tarball":"https://registry.npmjs.org/@andy0130tw/binary-search-tree/-/binary-search-tree-5.3.2-fork.1.tgz","fileCount":14,"unpackedSize":49344,"signatures":[{"keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U","sig":"MEQCIBnjSWsExk/qVR0EZVGcmC51F+UEV5Pk8cyS4isTcjf9AiAhgxQpcwZ7hVVlfslm19hKNv1hMLqXXOBudsocmFc0bA=="}]},"_npmUser":{"name":"andy0130tw","email":"andy0130tw@yahoo.com.tw"},"directories":{},"maintainers":[{"name":"andy0130tw","email":"andy0130tw@yahoo.com.tw"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/binary-search-tree_5.3.2-fork.1_1787501036794_0.3767891828023817"},"_hasShrinkwrap":false}},"time":{"created":"2025-05-25T13:54:26.605Z","modified":"2026-08-23T16:03:57.082Z","5.3.2-fork.0":"2025-05-25T13:54:26.904Z","5.3.2-fork.1":"2026-08-23T16:03:56.941Z"},"bugs":{"url":"https://github.com/datastructures-js/binary-search-tree/issues"},"author":{"name":"Eyas Ranjous","email":"eyas.ranjous@gmail.com"},"license":"MIT","homepage":"https://github.com/datastructures-js/binary-search-tree#readme","keywords":["binary search tree","bst js","bst es6","binary search tree es6","binary search tree js","avl tree","avl tree es6","avl tree js","self balancing tree"],"repository":{"type":"git","url":"git+https://github.com/datastructures-js/binary-search-tree.git"},"description":"binary search tree & avl tree (self balancing tree) implementation in javascript","maintainers":[{"name":"andy0130tw","email":"andy0130tw@yahoo.com.tw"}],"readme":"# @datastructures-js/binary-search-tree\n\n[![npm](https://img.shields.io/npm/v/@datastructures-js/binary-search-tree.svg)](https://www.npmjs.com/package/@datastructures-js/binary-search-tree)\n[![npm](https://img.shields.io/npm/dm/@datastructures-js/binary-search-tree.svg)](https://www.npmjs.com/package/@datastructures-js/binary-search-tree) [![npm](https://img.shields.io/badge/node-%3E=%206.0-blue.svg)](https://www.npmjs.com/package/@datastructures-js/binary-search-tree)\n\nBinary Search Tree & AVL Tree (Self Balancing Tree) implementation in javascript.\n\n\n\n# Contents\n* [Install](#install)\n* [require](#require)\n* [import](#import)\n* [API](#api)\n * [constructor](#constructor)\n * [insert](#insert)\n * [has](#has)\n * [hasKey](#haskey)\n * [find](#find)\n * [findKey](#findkey)\n * [min](#min)\n * [max](#max)\n * [lowerBound (floor)](#lowerbound-floor)\n * [lowerBoundKey (floorKey)](#lowerboundkey-floorkey)\n * [upperBound (ceil)](#upperbound-ceil)\n * [upperBoundKey (ceilKey)](#upperboundkey-ceilkey)\n * [root](#root)\n * [count](#count)\n * [traverseInOrder](#traverseinorder)\n * [traversePreOrder](#traversepreorder)\n * [traversePostOrder](#traversepostorder)\n * [remove](#remove)\n * [removeNode](#removeNode)\n * [clear](#clear)\n * [BinarySearchTreeNode](#binarysearchtreenodet)\n * [AvlTreeNode](#avltreenodet)\n * [Build](#build)\n * [License](#license)\n\n## install\n```sh\nnpm install --save @datastructures-js/binary-search-tree\n```\n\n### require\n\n```js\nconst {\n BinarySearchTree,\n BinarySearchTreeNode,\n AvlTree,\n AvlTreeNode\n} = require('@datastructures-js/binary-search-tree');\n```\n\n### import\n```js\nimport {\n BinarySearchTree,\n BinarySearchTreeNode,\n AvlTree,\n AvlTreeNode\n} from '@datastructures-js/binary-search-tree';\n```\n\n## API\n\n### constructor\nconstructor accepts a custom compare function to insert new values into the tree based on the returned number.\n\nthe compare function must return a number for the 3 cases:\n* less than 0 to place a value on the left.\n* greater than 0 to place a value on the right.\n* 0 for equal values.\n\nThere is already a default compare function for primitive values (number, string).\n\nconstructor also accepts an options param, where the comparison key prob name can be passed for object types in order to search by that key directly using findKey and hasKey.\n\n##### JS\n###### BinarySearchTree\n```js\nconst nums = new BinarySearchTree();\nconst employees = new BinarySearchTree(\n (a, b) => a.id - b.id,\n { key: 'id' }\n);\n```\n\n###### AvlTree\n```js\nconst nums = new AvlTree();\nconst employees = new AvlTree(\n (a, b) => a.id - b.id,\n { key: 'id' }\n);\n```\n\n##### TS\n```js\ninterface IEmployee {\n id: number;\n}\n```\n\n###### BinarySearchTree\n```js\nconst nums = new BinarySearchTree();\nconst employees = new BinarySearchTree((a, b) => a.id - b.id, { key: 'id' });\n```\n\n###### AvlTree\n```js\nconst nums = new AvlTree();\nconst employees = new AvlTree((a, b) => a.id - b.id, { key: 'id' });\n```\n\n### insert\nO(log(n))\n\ninserts a value into the tree and returns the inserted node. Inserting an node with existing value, will update the existing node's value with the new one.\n\n```js\nnums\n .insert(50)\n .insert(80)\n .insert(30)\n .insert(90)\n .insert(60)\n .insert(40)\n .insert(20);\n\nemployees\n .insert({ id: 50 })\n .insert({ id: 80 })\n .insert({ id: 30 })\n .insert({ id: 90 })\n .insert({ id: 60 })\n .insert({ id: 40 })\n .insert({ id: 20 });\n```\n\n### has\nO(log(n))\n\nchecks if a value exists.\n\n```js\nnums.has(50); // true\nnums.has(100); // false\n\nemployees.has({ id: 50 }); // true\nemployees.has({ id: 100 }); // false\n```\n\n### hasKey\nO(log(n))\n\nchecks if an object exists by its key if the comparison key prob is provided in the constructor.\n\n```js\nemployees.hasKey(50); // true\nemployees.hasKey(100); // false\n```\n\n### find\nO(log(n))\n\nfinds a value and returns its node.\n\n```js\nnums.find(60).getValue(); // 60\nnums.find(100); // null\n\nemployees.find({ id: 60 }).getValue(); // { id: 60 }\nemployees.find({ id: 100 }); // null\n```\n\n### findKey\nO(log(n))\n\nfinds a node by its object key if the comparison key prob is provided in the constructor.\n\n```js\nemployees.findKey(60).getValue(); // { id: 60 }\nemployees.findKey(100); // null\n```\n\n### min\nO(log(n))\n\nfinds the node with min value in the tree.\n\n```js\nnums.min().getValue(); // 20\n\nemployees.min().getValue(); // { id: 20 }\n```\n\n### max\nO(log(n))\n\nfinds the node with max value in the tree.\n\n```js\nnums.max().getValue(); // 90\n\nemployees.max().getValue(); // { id: 90 }\n```\n\n### lowerBound (floor)\nO(log(n))\n\nfinds the node with the biggest value less or equal a given value. You can eliminate equal values by passing second param as false. `.floor` is an alias to the same function.\n\n```js\nnums.lowerBound(60).getValue(); // 60\nnums.lowerBound(60, false).getValue(); // 50\nnums.lowerBound(10); // null\n\nemployees.floor({ id: 60 }).getValue(); // { id: 60 }\nemployees.floor({ id: 60 }, false).getValue(); // { id: 50 }\nemployees.floor({ id: 10 }); // null\n```\n\n### lowerBoundKey (floorKey)\nO(log(n))\n\nfinds the node with the biggest key less or equal a given key if the comparison key prob is provided in the constructor. You can eliminate equal values by passing second param as false. `.floorKey` is an alias to the same function.\n\n```js\nemployees.floorKey(60).getValue(); // { id: 60 }\nemployees.floorKey(60, false).getValue(); // { id: 50 }\nemployees.floorKey(10); // null\n```\n\n### upperBound (ceil)\nO(log(n))\n\nfinds the node with the smallest value bigger or equal a given value. You can eliminate equal values by passing second param as false. `.ceil` is an alias to the same function.\n\n```js\nnums.upperBound(75).getValue(); // 80\nnums.upperBound(80).getValue(); // 80\nnums.upperBound(80, false).getValue(); // 90\nnums.upperBound(110); // null\n\nemployees.ceil({ id: 75 }).getValue(); // { id: 80 }\nemployees.ceil({ id: 80 }).getValue(); // { id: 80 }\nemployees.ceil({ id: 80 }, false).getValue(); // { id: 90 }\nemployees.ceil({ id: 110 }); // null\n```\n\n\n### upperBoundKey (ceilKey)\nO(log(n))\n\nfinds the node with the smallest key bigger or equal a given key if the comparison key prob is provided in the constructor. You can eliminate equal values by passing second param as false. `.ceilKey` is an alias to the same function.\n\n```js\nemployees.ceilKey(75).getValue(); // { id: 80 }\nemployees.ceilKey(80).getValue(); // { id: 80 }\nemployees.ceilKey(80, false).getValue(); // { id: 90 }\nemployees.ceilKey(110); // null\n```\n\n### root\nO(1)\n\nreturns the root node of the tree.\n\n```js\nnums.root().getValue(); // 50\n\nemployees.root().getValue(); // { id: 50 }\n```\n\n### count\nO(1)\n\nreturns the count of nodes in the tree.\n\n```js\nnums.count(); // 7\n\nemployees.count(); // 7\n```\n\n### traverseInOrder\nO(n)\n\ntraverses the tree in order (left-node-right). it also accepts an optional second param as a callback to abort traversal when it returns true.\n\n```js\nnums.traverseInOrder((node) => console.log(node.getValue()));\n/*\n 20\n 30\n 40\n 50\n 60\n 80\n 90\n*/\n\nemployees.traverseInOrder((node) => console.log(node.getValue()));\n/*\n { id: 20 }\n { id: 30 }\n { id: 40 }\n { id: 50 }\n { id: 60 }\n { id: 80 }\n { id: 90 }\n*/\n\nlet counter = 0;\nconst abortCb = () => counter > 1;\nemployees.traverseInOrder((node) => {\n console.log(node.getValue());\n counter += 1;\n}, abortCb);\n/*\n { id: 20 }\n { id: 30 }\n*/\n```\n\n### traversePreOrder\nO(n)\n\ntraverses the tree pre order (node-left-right). it also accepts an optional second param as a callback to abort traversal when it returns true.\n\n```js\nnums.traversePreOrder((node) => console.log(node.getValue()));\n/*\n 50\n 30\n 20\n 40\n 80\n 60\n 90\n*/\n\nemployees.traversePreOrder((node) => console.log(node.getValue()));\n/*\n { id: 50 }\n { id: 30 }\n { id: 20 }\n { id: 40 }\n { id: 80 }\n { id: 60 }\n { id: 90 }\n*/\n\nlet counter = 0;\nconst abortCb = () => counter > 1;\nemployees.traversePreOrder((node) => {\n console.log(node.getValue());\n counter += 1;\n}, abortCb);\n/*\n { id: 50 }\n { id: 30 }\n*/\n```\n\n### traversePostOrder\nO(n)\n\ntraverses the tree post order (left-right-node). it also accepts an optional second param as a callback to abort traversal when it returns true.\n\n```js\nnums.traversePostOrder((node) => console.log(node.getValue()));\n/*\n 20\n 40\n 30\n 60\n 90\n 80\n 50\n*/\n\nemployees.traversePostOrder((node) => console.log(node.getValue()));\n/*\n { id: 20 }\n { id: 40 }\n { id: 30 }\n { id: 60 }\n { id: 90 }\n { id: 80 }\n { id: 50 }\n*/\n\nlet counter = 0;\nconst abortCb = () => counter > 1;\nemployees.traversePostOrder((node) => {\n console.log(node.getValue());\n counter += 1;\n}, abortCb);\n/*\n { id: 20 }\n { id: 40 }\n*/\n```\n\n### remove\nO(log(n))\n\nremoves a node from the tree by its value. The function will first find the node that corresponds to the value and then remove it. AVL tree will rotate nodes properly if the tree becomes unbalanced.\n\n```js\nnums.remove(20); // true\nnums.remove(100); // false\nnums.count(); // 6\n\nemployees.remove({ id: 20 }); // true\nemployees.remove({ id: 100 }); // false\nemployees.count(); // 6\n```\n\n### removeNode\nO(log(n))\n\nremoves a node from the tree by its reference.\n\n```js\nconst n20 = employees.findKey(20);\nemployees.removeNode(n20); // true\n\nconst n50 = employees.findKey(50);\nemployees.removeNode(n50); // true\n```\n\n### clear\nO(1)\n\nclears the tree.\n\n```js\nnums.clear();\nnums.count(); // 0\nnums.root(); // null\n\nemployees.clear();\nemployees.count(); // 0\nemployees.root(); // null\n```\n\n### BinarySearchTreeNode<T>\n\n#### setValue\nsets the node's value.\n\n#### getValue\ngets the node's value.\n\n#### setLeft\nsets the node's left child.\n\n#### getLeft\ngets the node's left child.\n\n#### hasLeft\nchecks if node has a left child.\n\n#### setRight\nsets the node's right child.\n\n#### getRight\ngets the node's right child.\n\n#### hasRight\nchecks if node has a right child.\n\n#### setParent\nsets the node's parent node.\n\n#### getParent\ngets the node's parent node.\n\n#### hasParent\nchecks if node has a parent node.\n\n#### isLeaf\nchecks if node is a leaf in the tree.\n\n#### isRoot\ncheck if node is the root node.\n\n### AvlTreeNode<T>\n#### setValue\nsets the node's value.\n\n#### getValue\ngets the node's value.\n\n#### setLeft\nsets the node's left child.\n\n#### getLeft\ngets the node's left child.\n\n#### hasLeft\nchecks if node has a left child.\n\n#### setRight\nsets the node's right child.\n\n#### getRight\ngets the node's right child.\n\n#### hasRight\nchecks if node has a right child.\n\n#### setParent\nsets the node's parent node.\n\n#### getParent\ngets the node's parent node.\n\n#### hasParent\nchecks if node has a parent node.\n\n#### isLeaf\nchecks if node is a leaf in the tree.\n\n#### isRoot\ncheck if node is the root node.\n\n#### rotateLeft\nRotates self left (counter-clockwise).\n\n#### rotateRight\nRotates self right (clockwise).\n\n#### rotateLeftRight\nRotates left child to left then self to right.\n\n#### rotateRightLeft\nRotates right child to right then self to left.\n\n#### getHeight\nGets the height of the node in the tree. root height is 1.\n\n#### getLeftHeight\nGets the height of left child. 0 if no left child.\n\n#### getRightHeight\nGets the height of right child. 0 if no right child.\n\n#### getBalance\nreturns the node's balance as the diff between left and right heights.\n\n#### isBalanced\nchecks if the node is balanced. (height diff is not more/less than 1/-1)\n\n## Build\n```\ngrunt build\n```\n\n## License\nThe MIT License. Full License is [here](https://github.com/datastructures-js/binary-search-tree/blob/master/LICENSE)\n","readmeFilename":"README.md"}