BinarySearchTree

DataStructure. BinarySearchTree

Organize data and with have the ability to efficiently access, search, insert and delete values while keeping them in a sorted order. Binary search trees are similar to linked lists in the sense that it is only necessary to update the immediately surrounding items when adding or removing a value.

Each node can have two children:

  • Left: Less than parent node's value
  • Right: Greater than parent node's value

Note: All values must be unique in the tree.

Example:
A sequence of numbers:
1 2 3 4 5 6 7
And turning it into a tree starting from the center.

This makes the traversal to find a value very efficient. Say we're trying to find the number 5 in our tree:

Only had to do 3 checks to reach the number 5.

Constructor

new BinarySearchTree()

The tree has to start with a single parent, the "root" of the tree.
Source:

Methods

add(value)

Add a new item to the tree. Start traversal through current nodes, bouncing between left and right nodes depending on them being less than or greater than the value. Add the value if a node is 'null'.
Parameters:
Name Type Description
value
Source:

contains(value) → {boolean}

Search through the tree it it contains the value.
Parameters:
Name Type Description
value * Value mathing to node in the tree
Source:
Returns:
Type
boolean