BST - binary search tree in Java and Python

Both Java and Python have ways to work with BST-like structures, though there’s a small nuance. Let me explain clearly.

---

1️⃣ Java

Java doesn’t have a “BST class” exactly, but it has TreeSet and TreeMap, which are implemented as balanced BSTs (Red-Black Trees internally).

TreeSet (just keys, sorted)

import java.util.*;

public class BSTExample {
    public static void main(String[] args) {
        TreeSet<Integer> bst = new TreeSet<>();

        bst.add(8);
        bst.add(5);
        bst.add(10);
        bst.add(3);
        bst.add(6);
        bst.add(12);

        System.out.println("BST elements in sorted order:");
        for (int val : bst) {
            System.out.print(val + " ");
        }
    }
}

Output:

3 5 6 8 10 12

TreeMap (key → value, sorted by keys)

TreeMap<Integer, String> map = new TreeMap<>();
map.put(8, "A");
map.put(5, "B");
map.put(10, "C");

System.out.println(map.firstKey()); // smallest key
System.out.println(map.lastKey());  // largest key

✅ Key points:

• TreeSet and TreeMap maintain sorted order automatically.
• They use balanced BST internally → O(log n) operations.

---

2️⃣ Python

Python doesn’t have a built-in BST class in the standard library, but you can use the bisect module (sorted arrays) or external libraries like bintrees.

Option 1: bisect (sorted array mimic)

import bisect

bst_list = []
for val in [8,5,10,3,6,12]:
    bisect.insort(bst_list, val)  # keeps list sorted

print(bst_list)

Output:

[3, 5, 6, 8, 10, 12]

Note: This is not a tree structure, but behaves like BST for insert + sorted order.

Option 2: bintrees library

pip install bintrees

from bintrees import AVLTree

tree = AVLTree()
for val in [8,5,10,3,6,12]:
    tree.insert(val, str(val))

print(list(tree.keys()))  # sorted keys

✅ AVLTree = self-balancing BST, keeps keys sorted.

---

🔹 Summary:

Language	Built-in BST-like option	Notes
Java	TreeSet, TreeMap	Red-Black Tree internally, sorted automatically
Python	bisect (array), bintrees (AVL/Red-Black)	bisect = sorted array, bintrees = proper BST

---