TreeSet - Notes By ShariqSP

TreeSet in Java

TreeSet is an implementation of the SortedSet interface in Java that stores elements in sorted order. It uses a Red-Black tree data structure to maintain the elements in sorted order, providing efficient retrieval and insertion operations.

Definition:

A TreeSet is a collection that stores unique elements in sorted order. It does not allow duplicate elements, and null elements are not permitted. Elements are sorted according to their natural ordering or a custom comparator provided by the user.

Methods:

• add(E element): Adds the specified element to the set if it is not already present.
• remove(Object obj): Removes the specified element from the set if it is present.
• contains(Object obj): Returns true if the set contains the specified element.
• isEmpty(): Returns true if the set contains no elements.
• size(): Returns the number of elements in the set.
• clear(): Removes all elements from the set.

Example:

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        // Create a TreeSet of integers
        TreeSet set = new TreeSet<>();

        // Add elements to the set
        set.add(10);
        set.add(5);
        set.add(20);

        // Display the elements
        System.out.println("Elements in the set:");
        System.out.println(set);

        // Remove an element
        set.remove(5);

        // Display the modified set
        System.out.println("\nElements after removal:");
        System.out.println(set);
    }
}
    

In this example, a TreeSet is created to store integers. Elements are added to the set using the add() method and removed using the remove() method.

Advantages and Disadvantages of TreeSet

Advantages:

• Sorted Order: TreeSet maintains elements in sorted order, either based on their natural ordering or a custom comparator provided at the time of TreeSet creation. This feature allows for efficient retrieval of elements in sorted order, making TreeSet suitable for scenarios where sorted data is required.
• Efficient Operations: TreeSet offers efficient performance for operations like insertion, deletion, and retrieval of elements. The time complexity for these operations is O(log n), where n is the number of elements in the TreeSet, due to its underlying red-black tree structure.
• Implements NavigableSet: TreeSet implements the NavigableSet interface, providing additional navigation methods for locating elements based on their position in the sorted set. These methods include ceiling, floor, higher, and lower, which can be useful for various search operations.

Disadvantages:

• Memory Overhead: TreeSet requires additional memory to maintain the balanced tree structure for sorting elements. This overhead can become significant when dealing with large datasets, especially if the elements are complex objects with large memory footprints.
• Complexity: TreeSet introduces complexity in terms of implementation and understanding due to its internal red-black tree structure. While this structure allows for efficient operations, it also makes TreeSet more complex compared to simpler data structures like HashSet.
• No Duplicates: TreeSet does not allow duplicate elements. If duplicate elements are added to a TreeSet, they are automatically ignored. While this ensures uniqueness of elements, it may not be suitable for scenarios where duplicate elements are required or where the order of duplicates matters.

Interview Questions and MCQs on TreeSet in Java

Interview Questions:

1. What is a TreeSet in Java?
2. How does TreeSet differ from HashSet and LinkedHashSet?
3. What is the significance of natural ordering in TreeSet?
4. How is TreeSet implemented internally?
5. Can TreeSet contain duplicate elements?
6. How do you add elements to a TreeSet?
7. How do you remove elements from a TreeSet?
8. What are the advantages and disadvantages of using TreeSet?

Multiple Choice Questions (MCQs):

1. Which interface does TreeSet implement?
   a) List
   b) Set
   c) Map
   d) Collection
   Answer: b) Set
2. How are elements stored internally in a TreeSet?
   a) Based on their hash codes
   b) Based on their indexes
   c) In insertion order
   d) In sorted order
   Answer: d) In sorted order
3. What happens when you try to add a duplicate element to a TreeSet?
   a) The element is added without any changes
   b) An exception is thrown
   c) The existing element is replaced with the new one
   d) The new element is ignored
   Answer: d) The new element is ignored
4. Which method is used to remove all elements from a TreeSet?
   a) removeAll()
   b) clear()
   c) deleteAll()
   d) erase()
   Answer: b) clear()
5. How do you check if a TreeSet contains a specific element?
   a) containsElement()
   b) contains()
   c) containsKey()
   d) containsValue()
   Answer: b) contains()