A binary search tree (BST) is a binary tree data structure where each node follows a specific ordering rule. The value of the left node is always less than the value of the parent node, and the value of the right node is always greater than the value of the parent node. This rule applies recursively to the left and right branches of the root node.
Let’s use an illustration to better comprehend the binary search tree concept.
In the illustration above, the first node has the value 5 and this node is called the root node. The node in the left subtree is smaller than the root node, while the node in the right subtree is larger.
Note: A node without a child node is known as the leaf node.
Let’s assume these data values 25, 15, 40, 65, 13, 30, 37 to demonstrate how to create a binary search tree.
We insert 25 into the tree. This will be the root node.
We insert 15 to the left node since 15 is less than the root node.
We insert 40 to the right node because it is greater than the root node.
We insert 65 to the subtree right of 40 since it is greater than 40 and the root node.
We insert 13 to the subtree left of 15 since it is less than 15 and the root node.
We insert 21 to the subtree right of 15 since it is greater than 15, but less than the root node.
We insert 37 to the subtree left of 40 since it is less than 40 and greater than the root node.
The following diagram is an illustration of our binary search tree.
The following code shows how to implement a binary search tree in Dart.
class TreeNode {int treeValue;TreeNode leftChildNode;TreeNode rightChildNode;TreeNode(this.treeValue);}class BinarySearchTree {//declares a variable named node of type NodeTreeNode treeRoot;// insert() methodvoid insertValue(int value) {TreeNode newTreeNode = TreeNode(value);if (treeRoot == null) {treeRoot = newTreeNode;} else {TreeNode currentValue = treeRoot;while (true) {if (value < currentValue.treeValue) {if (currentValue.leftChildNode == null) {currentValue.leftChildNode = newTreeNode;break;}currentValue = currentValue.leftChildNode;} else {if (currentValue.rightChildNode == null) {currentValue.rightChildNode = newTreeNode;break;}currentValue = currentValue.rightChildNode;}}}}// containsValue() methodbool containsValue(int value) {TreeNode currentNode = treeRoot;while (currentNode != null) {if (value == currentNode.treeValue) {return true;} else if (value < currentNode.treeValue) {currentNode = currentNode.leftChildNode;} else {currentNode = currentNode.rightChildNode;}}return false;}}void main() {// initiates object of the class BinarySearchTreeBinarySearchTree bst = BinarySearchTree();// Insert values in the tree using insert() methodbst.insertValue(25);bst.insertValue(15);bst.insertValue(40);bst.insertValue(65);bst.insertValue(13);bst.insertValue(21);bst.insertValue(37);// Checks if the value is in the tree using contains() methodprint("Does it contains the vale 65: ${bst.containsValue(65)}");print("Does it contains the vale 20: ${bst.containsValue(20)}");}
Lines 1-7: We create the class TreeNode
with properties treeValue
, leftChildNode
, and rightChildNode
. The TreeNode
class represents a node in the binary search tree and includes pointers to the left and right child nodes as well as a value for each node.
Lines 9-51: We define the BinarySearchTree
class which has two methods insertValue()
and containsValue()
. The tree is managed by the BinarySearchTree
class.
Line 11: We declare a variable called treeRoot
of type TreeNode
.
Lines 13-36: We define the insertValue()
method. The insert method involves moving up the tree from the root and comparing the value to be placed with the value of the current node. We shift to the left child node if the value is less, and to the right child node if the value is greater. This method is repeated until a blank space is found to add the new node.
Lines 38-50: We define the containsValue()
method. We compare the target value with the value of the current node starting from the root node. We return true
if the values match. If the target value is less, we shift to the left child node, and if it’s greater, we shift to the right child node. This process is repeated until the desired result is obtained or we reach a leaf node, in which case we return false
.
Line 55: We create a new instance of the BinarySearchTree
class called bst
.
Lines 58-64: We insert values into the tree using the insertValue()
method.
Lines 67-68: We pass a target value to the containsValue()
method to check if it exists in the tree. The result is displayed using the print()
function.
Free Resources