Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Introduction to a Binary Search Tree (BST)

Explore the structure of binary search trees and understand how nodes are ordered by key values. Learn key operations such as insertion, deletion, and traversal while applying binary tree concepts. This lesson helps you build a strong foundation for implementing BSTs effectively in Go.

We'll cover the following...

What is a BST?

A BST or a binary search tree is a binary tree in which nodes are ordered in the following way:

  • The key in the left node is less than the key in its parent node.
  • The key in the right node is greater than the key in its parent node.
  • No duplicate key is allowed.

Let’s look at the following figure to better understand a BST.

Here, the data in the left subtree nodes is less than the root node 6, and the data in the right subtree nodes is greater than the root node. This condition is true for every node in the above tree.

Some important pointers

Before moving forward, let’s keep the following points in mind:

  • There can be two separate key and value fields in the tree node. However, for simplicity, we’ll consider the value as the key.
  • All problems in the binary search tree are solved using this supposition that the value in the node is also the key for the tree.
  • Because a binary search tree is also a binary tree, all the algorithms of a binary tree (covered in the previous chapter) are applicable to a binary search tree.