What is time complexities insertions, deletion and retrieval of TreeSet and TreeMap?

TreeSet and TreeMap are sorted collections implemented using a self-balancing Red-Black Tree. Because of this tree-based structure, insertion, deletion, and retrieval operations require traversing the tree, resulting in O(log n) time complexity for most operations.

Key Points: • TreeSet and TreeMap maintain elements in sorted order. • Both are internally implemented using a Red-Black Tree. • Insertion, deletion, and retrieval operations take O(log n) time. • They provide predictable performance regardless of data size. • Sorting can be based on natural ordering or a custom Comparator.

Time Complexity of TreeSet

TreeSet stores unique elements in sorted order.

Insertion (add)

Time Complexity:

O(log n)

Reason:

• The Red-Black Tree finds the correct position. • The tree may rebalance itself after insertion.

Deletion (remove)

Time Complexity:

O(log n)

Reason:

• The element must be located. • Tree structure may need rebalancing.

Retrieval/Search (contains)

Time Complexity:

O(log n)

Reason:

• The tree is traversed from root to leaf. • Each comparison eliminates half of the remaining nodes.

Example:

TreeSet<Integer> numbers =
        new TreeSet<>();

numbers.add(30);
numbers.add(10);
numbers.add(20);

Output:

[10, 20, 30]

Time Complexity of TreeMap

TreeMap stores key-value pairs with keys maintained in sorted order.

Insertion (put)

Time Complexity:

O(log n)

Reason:

• Key position is determined within the Red-Black Tree. • Tree balancing may occur.

Deletion (remove)

Time Complexity:

O(log n)

Reason:

• Locate the key. • Remove the node. • Rebalance the tree if required.

Retrieval (get)

Time Complexity:

O(log n)

Reason:

• Search begins at the root. • Tree traversal locates the key efficiently.

Example:

TreeMap<Integer, String> employees =
        new TreeMap<>();

employees.put(102, "John");
employees.put(101, "David");

Output:

{101=David, 102=John}

Code Example:

import java.util.TreeMap;
import java.util.TreeSet;

public class Demo {

    public static void main(String[] args) {

        TreeSet<Integer> set =
                new TreeSet<>();

        set.add(30);
        set.add(10);
        set.add(20);

        TreeMap<Integer, String> map =
                new TreeMap<>();

        map.put(102, "John");
        map.put(101, "David");

        System.out.println(set);
        System.out.println(map);
    }
}

Output:

[10, 20, 30]

{101=David, 102=John}

Why O(log n)?

Red-Black Trees remain balanced.

Example:

For 1,000,000 elements:

Linear Search:

O(n)

May require checking up to 1,000,000 elements.

Red-Black Tree:

O(log n)

Requires approximately 20 comparisons.

This makes TreeSet and TreeMap highly efficient while maintaining sorted order.

Comparison with Hash-Based Collections

HashSet / HashMap:

• Average Insert → O(1) • Average Search → O(1) • Average Delete → O(1) • No sorting

TreeSet / TreeMap:

• Insert → O(log n) • Search → O(log n) • Delete → O(log n) • Elements remain sorted

When to Use TreeSet and TreeMap?

Use TreeSet when:

• Unique elements are required. • Data must remain sorted.

Use TreeMap when:

• Key-value pairs are required. • Keys must remain sorted.

Real-World Examples:

• Leaderboards • Ranking systems • Sorted employee records • Product catalogs • Range-based searches

Interview Tip: A concise interview answer is:

"TreeSet and TreeMap are implemented using a Red-Black Tree. Therefore, insertion, deletion, and retrieval operations have O(log n) time complexity. Unlike HashSet and HashMap, they automatically maintain elements in sorted order, making them suitable for scenarios where ordering is important."