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

Below is an example of the structural organization of elements in a binary search tree.

✏️ Implementations

This repository contains implementations in the following languages.

Click to access a particular implementation 👇.

Python	Typescript	C	C++	Kotlin

👀 See also

• The Binary Search Tree Wiki page.
• Convert a Binary Search Tree into a balanced tree.