Let’s take a look at how a Binary Search Tree works and how they are implemented in Javascript.
Basics of tree structure
In a Binary tree there are three things one should know first:
Root : This is the top node of a tree structure and it does not have a parent. In the example image above, 8 is a Root node.
Parent : It’s a predecessor node, of a node. In the above example 3, 10, 6, 14 are parent nodes.
Child : It’s a successors of a parent node. In the above example 1 and 6 are children of 3 and so on.
Binary tree
In binary tree structure each node can have maximum of two children. Child on left subtree is called left child and child on right subtree is called right child.
Binary search tree
BST is a binary tree but with a few conditions:
1) All the keys (data inside the node) are distinct.
2) In every parent node, the left child key value is smaller than the parent node key value.
3) In every parent node, the right child key value is larger than the parent node key value.
Insertion of a node
For insertion of a new node with key value , a program will find the right place and it will create a new empty node for data. If the key value already exists, insertion will be declined and the insertion operation terminates immediately without insertion — as a BST is not allowed to have duplicate keys.
Binary Search Tree implementation in Javascript
And that’s it! 🎉
If you like this article let me know in comments or tweet about it.
Top comments (0)