How to implement a binary search tree in Dart

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.

%0 node_1 5 node_2 2 node_1->node_2 node_3 9 node_1->node_3 node_1685338786304 1 node_2->node_1685338786304 node_1685338808217 12 node_2->node_1685338808217 node_1685338880035 4 node_3->node_1685338880035 node_1685338864351 20 node_3->node_1685338864351
Binary search tree

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.

Example

Let’s assume these data values 25, 15, 40, 65, 13, 30, 37 to demonstrate how to create a binary search tree.

  1. We insert 25 into the tree. This will be the root node.

  2. We insert 15 to the left node since 15 is less than the root node.

  3. We insert 40 to the right node because it is greater than the root node.

  4. We insert 65 to the subtree right of 40 since it is greater than 40 and the root node.

  5. We insert 13 to the subtree left of 15 since it is less than 15 and the root node.

  6. We insert 21 to the subtree right of 15 since it is greater than 15, but less than the root node.

  7. 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.

%0 node_1 25 node_2 15 node_1->node_2 node_3 40 node_1->node_3 node_1685338043765 13 node_2->node_1685338043765 node_1685338031866 21 node_2->node_1685338031866 node_1685338148085 37 node_3->node_1685338148085 node_1685337966764 65 node_3->node_1685337966764
Binary search tree Illustration

Code

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 Node
  TreeNode treeRoot;
// insert() method
  void 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() method
  bool 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 BinarySearchTree
  BinarySearchTree bst = BinarySearchTree();
  // Insert values in the tree using insert() method
  bst.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() method
  print("Does it contains the vale 65: ${bst.containsValue(65)}");
  print("Does it contains the vale 20: ${bst.containsValue(20)}");
}

Code explanation

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

Copyright ©2025 Educative, Inc. All rights reserved