Learn Data Structures and Algorithms with Golang

Binary search tree

A binary search tree is a data structure that allows for the quick lookup, addition, and removal of elements. It stores the keys in a sorted order to enable a faster lookup. This data structure was invented by P. F. Windley, A. D. Booth, A. J. T. Colin, and T. N. Hibbard. On average, space usage for a binary search tree is of the order O(n), whereas the insert, search, and delete operations are of the order O(log n). A binary search tree consists of nodes with properties or attributes:

• A key integer
• A value integer
• The leftNode and rightNode instances of TreeNode

They can be represented in the following code:

// TreeNode classtype TreeNode struct { key int value int leftNode *TreeNode  rightNode *TreeNode }

In the next ...