BTree

BTree main class

new BTree(attr: (BTreeRootAttrStruct | BTreeValueAttrStruct | T))
Parameters
attr ((BTreeRootAttrStruct | BTreeValueAttrStruct | T)) Can be of type object, string, number. In case of object root/value property is expected to be value of root node.
Example
new BTree(10);
new BTree({ root: 10 });
new BTree({ value: 10 });
Instance Members
depth
iterator
reduce

toString

Returns string value of given tree.

toString
Example
var tree = new BTree(10);
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.toString(); // "10102030"

toJSON

Returns JSON Form.

toJSON
Returns
BTreeNodeStruct: Returns json form of a given tree.
Example
var tree = new BTree(10);
tree.insert(20);
tree.toJSON(); // {value:10,lNode:{value:20,lNode:null,rNode:null},rNode:null}

toArray

Returns array value.

toArray
Returns
Array<BTreeNode>: Returns array form of given tree.
Example
var tree = new BTree(10);
tree.insert(20);
tree.toArray(); // => [{value:10,...},{value:20,...}]

toFlatArray

Returns array of values of the tree.

toFlatArray
Returns
Array<T>: Returns array form of given tree.
Example
var tree = new BTree(10);
tree.insert(20);
tree.toFlatArray(); // => [10,20]

insert

Inserts the given value to the tree where first free left child node is found.

insert
Parameters
val (any) any type of value to be added to tree node.
Returns
BTreeNode: Returns newly created BTreeNode.
Example
var tree = new BTree(10);
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.toString(); // "10102030"

insertLeftMost

Inserts the given value to the tree where first free left child node is found.

insertLeftMost
Parameters
val (T) any type of value to be added to tree node.
Returns
BTreeNode<T>: Returns newly created BTreeNode.

insertRightMost

Inserts the given value to the tree where first free right child node is found.

insertRightMost
Parameters
val (T) any type of value to be added to tree node.
Returns
BTreeNode<T>: Returns newly created BTreeNode.

delete

Deletes given value from tree. Travarsal = Root -> L -> R.

delete
Parameters
val (T) Value to be removed.
Returns
BTreeNode<T>: Returns removed BTreeNode.

insertAt

Inserts given element at given location. If location is already taken then it does not insert any value.

insertAt
Parameters
val (T) value to insert.
index (number) index at which to append new element to.
Throws
  • any: UnreachableError
Example
tree.insertAt(20,2);

traverseBFS

Breadth first search. Executes given callback functions with parameters BTreeNode and path index for each node in BFS fashion.

traverseBFS
Returns
void: no value.

traverseDFS

Depth first search, Executes given callback functions with parameters BTreeNode and path index for each node in DFS fashion.

traverseDFS
Returns
void: no value.

each

Breadth first search. Executes given callback functions with parameters BTreeNode and path index for each node in BFS fashion.

each
Returns
void: no value.

forEach

Breadth first search. Executes given callback functions with parameters BTreeNode and path index for each node in BFS fashion.

forEach
Returns
void: no value.

entries

Returns an iterable of key, value pairs for every entry in the tree.

entries
Returns
IterableIterator<[number, BTreeNode<T>]>: Iterable for iterations.
Example
var tree = new BTree(10);
for (const [index, node] of tree.entries()) {
 console.log(index, node.value); // 0, 10
}

map

Maps current tree values to a new tree with modifying the values using given callback function. Uses BFS.

map
Returns
BTree<T>: A new BTree
Example
var tree = BTree.fromArray([10, 20, 30, 40]);
var tree2 = tree.map(n => n * 2);
var arr2 = tree2.toArray(); // [{value:20,...},{value:40,...},{value:60,...},{value:80,...}]

filter

Filters each item based on given filter function

filter
Returns
BTree<T>: New filtered instance of tree.
Throws
  • any: FilteredRootError, Error when root node gets filtered out.
Example
var tree = BTree.fromArray([10, 20, 30, 40]);
var tree2 = tree.filter(n => !!(n % 4 === 0 || n === 10));
var arr2 = tree2.toArray(); // [{value:10,...},{value:20,...},{value:40,...}]

reverse

Reverses the current Binary Tree, Left Node becomes Right node and vise versa. Does not return new instance, returns current tree instance.

reverse
Returns
BTree<T>: Returns current tree instance.
Example
var tree = BTree.fromArray([10, 20, 30, 40, 50, 60, 70, 80]);
tree.reverse().toArray(); // => [10, 30, 20, 70, 60, 50, 40, 80]

indexOf

Returns first index of a value matched, if it is not present, it returns -1.

indexOf
Parameters
value (T) Any value to find.
Returns
number: Returns index of given item.
Example
var tree = BTree.fromArray([10, 20, 30, 40, 50, 60, 70, 80]);
tree.indexOf(30); // => 3
tree.indexOf(51); // => -1

includes

Checks if given item exists or not, returns boolean.

includes
Parameters
value (T) Any value to check if it exists or not.
Returns
boolean: Returns true if it is present, otherwise false.
Example
var tree = BTree.fromArray([10, 20, 30, 40, 50, 60, 70, 80]);
tree.includes(30); // true
tree.includes(51); // false

exists

Checks if given item exists or not, returns boolean.

exists
Parameters
value (T) Any value to check if it exists or not.
Returns
boolean: Returns true if it is present, otherwise false.
Example
var tree = BTree.fromArray([10, 20, 30, 40, 50, 60, 70, 80]);
tree.exists(30); // true
tree.exists(51); // false

has

Checks if given item exists or not, returns boolean.

has
Parameters
value (T) Any value to check if it exists or not.
Returns
boolean: Returns true if it is present, otherwise false.
Example
var tree = BTree.fromArray([10, 20, 30, 40, 50, 60, 70, 80]);
tree.has(30); // true
tree.has(51); // false

sort

Sorts the tree based on compare function, Has option to sort only at children level.

sort
Parameters
compareFnc (Function) Function used to determine the order of the elements. It is expected to return a negative value if first argument is less than second argument, zero if they're equal and a positive value otherwise. If omitted, the elements are sorted in ascending, ASCII character order.
(a, b) => a - b)
atOnlyFirstChildLevel (boolean) Optiona, Flag to specify if first child of each node should sorted. Default is false .
Returns
void: Returns undefined.
Example
var tree = BTree.fromArray([10, 200, 100, 50, 60, 90, 5, 3]);
tree.sort().toFlatArray(); // => [3,5,10,50,60,90,100,200]

print

Prints entire tree on the console, useful for logging and checking status.

print
Returns
void: Returns undefined.
Example
var tree = BTree.fromArray([1, 2, 3]);
tree.print();
1 (1)
|- 2 (2)
|- 3 (3)

find

Returns the first matched tree node. Traverses using BFS.

find
Parameters
item (T) any value to find inside the tree.
Returns
(BTreeNode<T> | null): Returns the first matched tree node, if not found, returns null.

getIndexFromPath

Returns index value from given path.

getIndexFromPath
Parameters
path (Array<("U" | "L" | "R")>) Array for U L or R, which represents the quickest path to get to a node.
Returns
number: Returns index value.

getPathFromIndex

Returns Path equivalent to the given index.

getPathFromIndex(index: number): Array<("U" | "L" | "R")>
Parameters
index (number) Index number from which path to be calculated.
Returns
Array<("U" | "L" | "R")>: Path equivalent to the given index.

fromArray

Converts given values into a Binary Tree.

fromArray(arr: Array<T2>): BTree<T2>
Parameters
arr (Array<T2>) Any array of values.
Returns
BTree<T2>: Newly generated tree.
Example
var tree = BTree.fromArray([10,20,30,40]);

BTreeNode

Binary Tree node class, contains 2 child nodes and single value.

new BTreeNode()
Example
var node = new BTreeNode({ value: 15 });
var node3 = new BTreeNode({ value: 30 });
var node2 = new BTreeNode({ value: 20, rNode: node, lNode: node3 });
console.log(node2.lNode.value); // 30
Instance Members
validate()
toJSON()
toString()
getDepth()