binary-search-trees

Description

This package contains :

Tree

A factory that when invoked (with an array as argument) create a Binary Search Tree (BST). The factory come with some functions :

• getRoot : Return the root node of the tree
• insert(value) : Insert the given value into the tree
• deleteItem(value) : Remove the node with the given value from the tree
• find(value) : Return the node with the given value
• levelOrder(callback ?) : If a callback function is passed, call it for each node, in Breadth-first level order. If nothing is passed, return an array containing all the values
• inOrder(callback ?) : If a callback function is passed, call it for each node, in Depth-first order (In-order). If nothing is passed, return an array containing all the values
• preOrder(callback ?) : If a callback function is passed, call it for each node, in Depth-first order (Pre-order). If nothing is passed, return an array containing all the values
• postOrder(callback ?) : If a callback function is passed, call it for each node, in Depth-first order (Post-order). If nothing is passed, return an array containing all the values
• height(node) : Return the height of a given node
• depth(node) : Return the depth of a given node
• isBalanced : Return true if the tree is balanced, else false. A balanced tree is a tree where for every node, the difference between heights of its left-subtree and its right-subtree is not more than 1.
• rebalance : Rebalance the tree

Note

A Node class is called to create each node. The node constructor expect to receive one argument, value.

A Node value can be accessed by node.data, its left-subtree by node.left and its right-subtree by node.right.

Keep in mind that the rebalance function won't change anything if the tree is balanced and that it isn't called automatically if isBalanced returns false. Same as the insert function doesn't check if the tree is balanced neither rebalance the tree after adding a new element.