TreeSet / Binary Search Tree

📋 Quick Reference

Property	Value
Type	Sorted set backed by Red-Black Tree
Add/Remove/Contains	O(log n)
First/Last	O(log n)
Memory	O(n) with node overhead
Ordering	Natural order or custom Comparator
Best For	Sorted unique elements, range queries

One-liner: Self-balancing BST providing O(log n) sorted operations with no duplicates.

🎮 Interactive Visualizer

Watch how TreeSet maintains balance during insertions and deletions:

TreeSet Operations (BST)
Avg: O(log n)Worst: O(n)
1 / 0
TreeSet vs HashSet:TreeSet keeps elements sorted, HashSet is faster but unordered
✓ Use for:Sorted unique elements, range queries, floor/ceiling operations
🌳 Binary Search Tree Property
left < node < right
All values in left subtree are smaller • All values in right subtree are larger
Java's TreeSet uses Red-Black Tree (self-balancing) for guaranteed O(log n) operations
Ready for operation...
Binary Search Tree
Traversal Path:No path yet
Pseudocode
1function add(value):
2  if root == null:
3    root = new Node(value)
4    return
5  node = root
6  while true:
7    if value < node.value:
8      if node.left == null:
9        node.left = new Node(value)
10        return
11      node = node.left
12    else if value > node.value:
13      if node.right == null:
14        node.right = new Node(value)
15        return
16      node = node.right
17    else: return // duplicate
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Path
Path
Current/Insert
Current/Insert
Found
Found
Not found
Not found
P · [ ] · R
Loading visualizer...

Try these operations:

Insert elements - see tree balancing (rotations)
Delete a node - watch restructuring
Find an element - observe O(log n) path
Try inserting duplicates - they're ignored!

🔧 Key Operations

Creating

JAVA(9 lines)
Code
Loading syntax highlighter...

Adding/Removing

JAVA(7 lines)
Code
Loading syntax highlighter...

Querying

JAVA(7 lines)
Code
Loading syntax highlighter...

JAVA(15 lines)
Code
Loading syntax highlighter...

Iteration

JAVA(8 lines)
Code
Loading syntax highlighter...

📊 Complexity Analysis

Operation	Time	Notes
`add(e)`	O(log n)	Tree traversal + possible rebalancing
`remove(e)`	O(log n)	Find + restructure
`contains(e)`	O(log n)	Binary search in tree
`first/last`	O(log n)	Traverse to leftmost/rightmost
`floor/ceiling`	O(log n)	Modified binary search
`subSet/headSet/tailSet`	O(1)	Returns view, not copy
`iteration`	O(n)	In-order traversal

Red-Black Tree Properties

1. Every node is RED or BLACK
2. Root is BLACK
3. Leaves (NIL) are BLACK
4. RED node → both children BLACK
5. All paths from node to leaves have same BLACK count

These rules ensure: height ≤ 2 × log(n+1)

✅ When to Use TreeSet

Good Use Cases

Sorted unique elements - always in order
Range queries - subSet, headSet, tailSet
Finding neighbors - floor, ceiling, lower, higher
Min/Max operations - first(), last()

Avoid When

Just need uniqueness - use HashSet (O(1) vs O(log n))
Frequent contains checks - HashSet is faster
Need index access - TreeSet has no get(i)
Null elements needed - TreeSet doesn't allow null

🔄 TreeSet vs HashSet vs LinkedHashSet

Feature	HashSet	LinkedHashSet	TreeSet
Order	None	Insertion	Sorted
add/contains	O(1)	O(1)	O(log n)
Memory	Lowest	Medium	Highest
Null allowed	Yes	Yes	No
Range queries	No	No	Yes

JAVA(4 lines)
Code
Loading syntax highlighter...

⚠️ Common Pitfalls

1. Inconsistent Comparator with equals

JAVA(10 lines)
Code
Loading syntax highlighter...

2. Mutating Elements After Insert

JAVA(10 lines)
Code
Loading syntax highlighter...

3. Using Non-Comparable Types

JAVA(6 lines)
Code
Loading syntax highlighter...

4. Expecting O(1) Like HashSet

JAVA(8 lines)
Code
Loading syntax highlighter...

🎤 Interview Tips

Q: What's the difference between TreeSet and HashSet?

"

TreeSet maintains sorted order using a Red-Black tree (O(log n) operations), while HashSet uses hashing (O(1) average). Choose TreeSet when you need sorted iteration or range queries; HashSet otherwise.

Q: Why can't TreeSet contain null?

"

TreeSet relies on comparisons to position elements. Comparing with null would throw NullPointerException. HashSet allows one null because it uses equals() for comparison.

Q: How does TreeSet handle duplicates?

"

Elements are compared using compareTo() or the Comparator. If comparison returns 0, elements are considered equal and the duplicate is not added. This is why Comparator should be consistent with equals().

Q: What's floor() vs lower()?

"

floor(e) returns greatest element ≤ e (inclusive), lower(e) returns greatest element < e (exclusive). Similarly, ceiling is ≥ and higher is >.

Previous: Part 3: HashMap

Next: Part 5: PriorityQueue / Heap

Visualizer: TreeSet from @tomaszjarosz/react-visualizers