Card 06/ 09
Binary Search Tree in Python, Java and TypeScript
Insert, search, delete and in-order traversal, then Java's TreeMap as the balanced built-in.
A binary search tree in code is a node with a key and two links, wrapped in a class that keeps the root and offers insert, search, delete and an in-order listing. This card covers one implementation in each of Python, Java and TypeScript, and then the balanced tree that Java's standard library already provides.
Each listing inserts 4, 2, 6, 1, 3, 5, 7, searches for 5 and 8, deletes 4, then deletes 1 and 6. Insert and delete are recursive and return the root of the subtree they were given, so a parent can reassign its link to whatever comes back: a new leaf, the same node, or a child moving up. That one idiom handles all three delete cases without tracking the parent separately. Search is a loop, since it changes nothing and needs no return path. Ignoring an equal key is the duplicate rule throughout.
The highlighted lines are the places the ordering does its work: where a new leaf is created, where the search chooses a side, and the two-child delete, which walks to the leftmost node of the right subtree, copies its key up and deletes it from the right. Java's listing ends with a TreeMap, highlighted too.
One binary search tree's insert, search and delete, in each language
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self._insert(self.root, key)
def _insert(self, node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = self._insert(node.left, key)
elif key > node.key:
node.right = self._insert(node.right, key)
return node
def contains(self, key):
node = self.root
while node is not None and node.key != key:
node = node.left if key < node.key else node.right
return node is not None
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return None
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
elif node.left is None:
return node.right
elif node.right is None:
return node.left
else:
successor = node.right
while successor.left is not None:
successor = successor.left
node.key = successor.key
node.right = self._delete(node.right, successor.key)
return node
def in_order(self):
keys = []
self._in_order(self.root, keys)
return keys
def _in_order(self, node, keys):
if node is not None:
self._in_order(node.left, keys)
keys.append(node.key)
self._in_order(node.right, keys)
tree = BinarySearchTree()
for key in (4, 2, 6, 1, 3, 5, 7):
tree.insert(key)
print("in order:", *tree.in_order())
print("contains 5:", tree.contains(5), "| contains 8:", tree.contains(8))
tree.delete(4)
print("after deleting 4:", *tree.in_order(), "| root:", tree.root.key)
tree.delete(1)
tree.delete(6)
print("after deleting 1 and 6:", *tree.in_order(), "| root:", tree.root.key)in order: 1 2 3 4 5 6 7
contains 5: True | contains 8: False
after deleting 4: 1 2 3 5 6 7 | root: 5
after deleting 1 and 6: 2 3 5 7 | root: 5import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;
public class BinarySearchTreeCode {
static final class Node {
int key;
Node left;
Node right;
Node(int key) {
this.key = key;
}
}
static final class BinarySearchTree {
Node root;
void insert(int key) {
root = insert(root, key);
}
private Node insert(Node node, int key) {
if (node == null) {
return new Node(key);
}
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
}
return node;
}
boolean contains(int key) {
Node node = root;
while (node != null && node.key != key) {
node = key < node.key ? node.left : node.right;
}
return node != null;
}
void delete(int key) {
root = delete(root, key);
}
private Node delete(Node node, int key) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = delete(node.left, key);
} else if (key > node.key) {
node.right = delete(node.right, key);
} else if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
Node successor = node.right;
while (successor.left != null) {
successor = successor.left;
}
node.key = successor.key;
node.right = delete(node.right, successor.key);
}
return node;
}
List<Integer> inOrder() {
List<Integer> keys = new ArrayList<>();
inOrder(root, keys);
return keys;
}
private void inOrder(Node node, List<Integer> keys) {
if (node != null) {
inOrder(node.left, keys);
keys.add(node.key);
inOrder(node.right, keys);
}
}
}
static String spaced(List<Integer> keys) {
return String.join(" ", keys.stream().map(String::valueOf).toList());
}
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
for (int key : new int[] {4, 2, 6, 1, 3, 5, 7}) {
tree.insert(key);
}
System.out.println("in order: " + spaced(tree.inOrder()));
System.out.println("contains 5: " + tree.contains(5) + " | contains 8: " + tree.contains(8));
tree.delete(4);
System.out.println("after deleting 4: " + spaced(tree.inOrder()) + " | root: " + tree.root.key);
tree.delete(1);
tree.delete(6);
System.out.println("after deleting 1 and 6: " + spaced(tree.inOrder()) + " | root: " + tree.root.key);
TreeMap<Integer, String> scores = new TreeMap<>();
for (int key : new int[] {4, 2, 6, 1, 3, 5, 7}) {
scores.put(key, "key " + key);
}
System.out.println("TreeMap keys from 2 to 5: " + scores.subMap(2, true, 5, true).keySet());
System.out.println("TreeMap first key: " + scores.firstKey() + " | next key above 4: " + scores.higherKey(4));
}
}in order: 1 2 3 4 5 6 7
contains 5: true | contains 8: false
after deleting 4: 1 2 3 5 6 7 | root: 5
after deleting 1 and 6: 2 3 5 7 | root: 5
TreeMap keys from 2 to 5: [2, 3, 4, 5]
TreeMap first key: 1 | next key above 4: 5type TreeNode = { key: number; left: TreeNode | null; right: TreeNode | null };
class BinarySearchTree {
root: TreeNode | null = null;
insert(key: number): void {
this.root = this.insertInto(this.root, key);
}
private insertInto(node: TreeNode | null, key: number): TreeNode {
if (node === null) {
return { key, left: null, right: null };
}
if (key < node.key) {
node.left = this.insertInto(node.left, key);
} else if (key > node.key) {
node.right = this.insertInto(node.right, key);
}
return node;
}
contains(key: number): boolean {
let node = this.root;
while (node !== null && node.key !== key) {
node = key < node.key ? node.left : node.right;
}
return node !== null;
}
delete(key: number): void {
this.root = this.deleteFrom(this.root, key);
}
private deleteFrom(node: TreeNode | null, key: number): TreeNode | null {
if (node === null) {
return null;
}
if (key < node.key) {
node.left = this.deleteFrom(node.left, key);
} else if (key > node.key) {
node.right = this.deleteFrom(node.right, key);
} else if (node.left === null) {
return node.right;
} else if (node.right === null) {
return node.left;
} else {
let successor = node.right;
while (successor.left !== null) {
successor = successor.left;
}
node.key = successor.key;
node.right = this.deleteFrom(node.right, successor.key);
}
return node;
}
inOrder(): number[] {
const keys: number[] = [];
const visit = (node: TreeNode | null): void => {
if (node !== null) {
visit(node.left);
keys.push(node.key);
visit(node.right);
}
};
visit(this.root);
return keys;
}
}
const tree = new BinarySearchTree();
for (const key of [4, 2, 6, 1, 3, 5, 7]) {
tree.insert(key);
}
console.log(`in order: ${tree.inOrder().join(" ")}`);
console.log(`contains 5: ${tree.contains(5)} | contains 8: ${tree.contains(8)}`);
tree.delete(4);
console.log(`after deleting 4: ${tree.inOrder().join(" ")} | root: ${tree.root?.key}`);
tree.delete(1);
tree.delete(6);
console.log(`after deleting 1 and 6: ${tree.inOrder().join(" ")} | root: ${tree.root?.key}`);in order: 1 2 3 4 5 6 7
contains 5: true | contains 8: false
after deleting 4: 1 2 3 5 6 7 | root: 5
after deleting 1 and 6: 2 3 5 7 | root: 5All three printed the keys 1 to 7 in order, found 5 and not 8, and after deleting 4 had 5 at the root, its successor. After the next two deletes, 2 3 5 7 remained. Every operation costs O(h) for a tree of height h: about log n when the keys arrive in a random order, and n - 1 when they arrive sorted. The recursion is as deep as the path it follows, so on a chain these versions can run out of call stack where a loop would not.
None of these trees rebalances, which is the reason to reach for a library in real code. Java's TreeMap is a red-black tree, a binary search tree that recolours and rotates a few nodes after each change so its height stays O(log n) for any insertion order. A rotation is a local rearrangement of a parent and child that keeps the in-order sequence unchanged. TreeMap guarantees O(log n) for get, put and remove, and adds the operations a sorted structure makes cheap. In the run, subMap(2, true, 5, true) returned the keys from 2 to 5 inclusive, firstKey returned 1, and higherKey(4), the smallest key above 4, returned 5. TreeSet offers the same for keys without values.
Python's standard library and JavaScript's built-in objects have no sorted map. dict and Map keep keys in insertion order, not sorted order. The usual stand-ins in Python are a list kept sorted with the bisect module, which finds a position in O(log n) but inserts in O(n), or a third-party package; in TypeScript, a third-party package or a tree like the one above.
← → move through sections and cards