There are many different data structures that serve many purposes and some can be more difficult to use than others. Some lack efficiency but are easy to use vice versa, a great data structure that is consistent in space and time efficiency is binary search tree or BST. For this blog we will be focusing on how to structure and use a binary search tree.
If you are not familiar Binary search trees are node based sorted binary trees in which all nodes left of the root are less and all nodes greater than the root are more. Basically if you take the list [1, 3, 4, 6, 7, 8, 10, 13, 14] so you first take the median number which in this case is 8, then take the all the values to the left and then organize them by the same rules in a subtree and so on, then do the same to all the values on the right of 8. Here is how it looks mapped out.
I will binary search tree is also setup with two simple constructors, but which will help you understand how they work.
// Node class
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Binary Search tree class
class BinarySearchTree
{
constructor()
{
// root of a binary seach tree
this.root = null;
}
// function to be implemented
// insert(data)
// remove(data)
// Helper function
// findMinNode()
// getRootNode()
// inorder(node)
// preorder(node)
// postorder(node)
// search(node, data)
} The main reason to use binary search trees is there simplicity and run time there space is always O(n), insert() runs at average O(log n) and worst of O(n) and same for search and traversal is O(n). If you see in the BinarySearchTree class, there’s some helper functions we need to create so let’s start with insert. To insert we will need to walk down the tree and find where the value is needed. We must compare the value to the root and if its less then walk down the tree to the left then compare to the next node value, if its greater than the next node value then walk down to the right. Here is how we implement the insert in code.
<!-- /* Font Definitions */ @font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:3 0 0 0 1 0;} @font-face {font-family:Consolas; panose-1:2 11 6 9 2 2 4 3 2 4; mso-font-charset:0; mso-generic-font-family:modern; mso-font-pitch:fixed; mso-font-signature:-520092929 1073806591 9 0 415 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman",serif; mso-fareast-font-family:"Times New Roman";} code {mso-style-noshow:yes; mso-style-priority:99; font-family:"Courier New"; mso-ascii-font-family:"Courier New"; mso-fareast-font-family:"Times New Roman"; mso-hansi-font-family:"Courier New"; mso-bidi-font-family:"Courier New";} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-family:"Calibri",sans-serif; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Calibri; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} @page WordSection1 {size:8.5in 11.0in; margin:1.0in 1.0in 1.0in 1.0in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.WordSection1 {page:WordSection1;} -->
// Method to insert a node in a tree
// it moves over the tree to find the location
// to insert a node with a given data
insertNode(node, newNode)
{
// if the data is less than the node
// data move left of the tree
if(newNode.data < node.data)
{
// if left is null insert node here
if(node.left === null)
node.left = newNode;
else
// if left is not null recur until
// null is found
this.insertNode(node.left, newNode);
}
// if the data is more than the node
// data move right of the tree
else
{
// if right is null insert node here
if(node.right === null)
node.right = newNode;
else
// if right is not null recur until
// null is found
this.insertNode(node.right,newNode);
}
} So, now you know the basics of how to implement and create a insert function of binary tree, hope this blog helps.
Sources
I Feel All Sorts of Ways About Programming 