binary-search-tree

A set of idiomatic implementations of a binary-search tree in multiple languages.

Current version: 1.0.0

📋 Table of content

Description
Implementations
See also

🔰 Description

This repository contains idiomatic implementations of a Binary Search Tree in multiple programming languages. The purpose of this repository is purely educational and aims to introduce a binary search tree recursive data structure, as well as its many implementation details across multiple languages.

A binary search tree is a tree data structure that can store arbitrarily typed data by enforcing the following properties :

The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
It doesn't have any duplicate nodes.

A binary search tree supports operations like search, insertion, deletion, min-max search, in $O(h)$ time where $h$ is the height of the tree. In a fully balanced binary search tree, the complexity of these operations tends to $O(\log{}n)$, where $n$ is the number of nodes in the tree. In the worst case scenario of a fully unbalanced tree, the complexity tends to $O(n)$.