TreeMap internal working.

Hook: TreeMap is like a library shelf that stays alphabetically sorted while you keep adding books—interviewers love it because it tests both sorted collections and tree internals.

Question: What is the internal working of TreeMap in Java?

Answer: TreeMap stores entries in sorted key order using a red-black tree, which is a self-balancing binary search tree. That means search, insert, and delete usually take O(log n) time. It keeps keys ordered by either a supplied Comparator or the keys’ natural ordering, and it also supports fast navigation like firstKey(), ceilingKey(), and range views such as subMap().

Interview-Ready Answer: I’d say TreeMap is a sorted map backed by a red-black tree. Each operation compares keys step by step down the tree, then may rebalance with recoloring and rotations, so get, put, and remove are O(log n). The big idea is that ordering is based on a comparator or natural order, and that also means equality is decided by comparison result 0, not by equals().

What TreeMap is

Detailed Explanation: TreeMap is Java’s sorted map implementation. A map stores key -> value pairs, and TreeMap keeps the keys in sorted order at all times. Under the hood, it uses a red-black tree, which is a binary search tree that stays balanced by using node colors and a few local fixes after updates.

How it works under the hood

1. Find the comparison rule. If you pass a Comparator, TreeMap uses it. If not, it expects keys to implement Comparable and uses natural ordering.
2. Search like a binary search tree. For a key, it starts at the root and compares left or right until it finds the key or reaches a null child.
3. Insert the new node. If the key is not present, TreeMap links a new node at the leaf position just like a normal binary search tree.
4. Fix balance. A new node is usually inserted red. If that breaks red-black rules, TreeMap performs recoloring and sometimes rotations (small tree rearrangements) to restore balance.
5. Handle duplicate keys. If comparison says two keys are equal (compare(...) == 0), the old value is replaced. This is a key gotcha: TreeMap uses ordering, not equals(), to decide key uniqueness.
6. Remove safely. Deletion may replace a node with its in-order successor, then perform more recoloring and rotations if needed.

A red-black tree keeps its height small. In practice, the height is bounded to about 2 * log2(n + 1), so even with 1,000,000 entries, the tree height stays around 40 or less. That is why TreeMap remains predictable under load.

Why it is fast and when to use it

Use TreeMap when you need sorted keys, range queries, or the nearest key before/after a target. Examples: scheduling, leaderboards by score, time-based lookups, and building views like headMap, tailMap, and subMap.

Do not choose it just for faster raw lookup. A hash-based map is usually faster for plain key lookup if you do not need ordering.

Comparison with other maps

Memory and edge cases: each TreeMap node stores extra pointers for parent, left, and right, plus a color flag. So it uses more memory than HashMap. Also, natural-order TreeMap does not allow null keys because it must compare keys; a custom comparator can allow null if it is written to handle it.

Important view behavior

subMap(), headMap(), and tailMap() return backed views, meaning they are not copies. A change in the view changes the original map, and a valid change in the original map can appear in the view. Getting the starting point costs O(log n); iterating over the returned range is linear in the number of items returned.

Complexity summary

• get, put, remove: O(log n)
• firstKey, lastKey, floorKey, ceilingKey: O(log n)
• Iteration over all entries: O(n)
• Range iteration: O(log n + k), where k is the number of returned entries

Memory hook: think of TreeMap as a sorted hallway with checkpoints: every key walks left or right, then the tree does a few quick posture fixes so the hallway never becomes a long, slow corridor.

Real-World Example: In a checkout service, you might store discount rules by minimum cart value: 100 -> 5%, 200 -> 10%, 500 -> 20%. When a user checks out with 275, the system can use floorEntry(275) to find the best applicable discount quickly.

What goes wrong when the team misunderstands TreeMap? A developer uses a comparator that compares only by minute of the day, so two promotions starting at 10:15 and 10:15 are treated as the same key. One rule silently overwrites the other, causing some customers to get the wrong discount. In logs, the map size is smaller than the config file, and support sees complaints like 'promo not applied' even though the rule exists in source control.

That bug is painful because nothing crashes. TreeMap is doing exactly what it was told: if comparison says two keys are equal, only one entry can live there.

Follow-up & Tricky Questions:

• What is the difference between TreeMap and HashMap? TreeMap keeps keys sorted and gives O(log n) operations, while HashMap gives average O(1) operations but no order.
• Why does TreeMap need keys to be Comparable or a Comparator? Because it must know whether to go left or right while walking the tree. Without a comparison rule, it cannot place a key correctly.
• What is a red-black tree? It is a balanced binary search tree where node colors and rotation rules keep the height small, which prevents worst-case linear chains.
• Are subMap, headMap, and tailMap copies? No, they are backed views. Updating the view updates the original TreeMap, and vice versa if the change stays within the view’s range.
• Does TreeMap use equals() to find duplicate keys? No, it uses comparison. If compare(a, b) == 0, TreeMap treats them as the same key even when equals() says they are different.
• Can TreeMap be used from multiple threads safely? Not by itself. If multiple threads write to it, you need external synchronization or a concurrent alternative like ConcurrentSkipListMap.
• Does iteration cost O(log n) per entry? No. Walking through entries is linear overall; the tree is already ordered, so iteration just follows links in sequence.
• Can TreeMap store null values? Yes, values may be null. The restriction is on keys in natural-order maps, because keys must be comparable.
• Tricky: If two different objects compare as equal, will both be stored? No. Only one entry survives, and the later put replaces the earlier value.
• Tricky: Is TreeMap faster than HashMap because it is sorted? No. Sorted behavior costs extra comparisons and balancing, so it is usually slower for plain lookups.

Common Mistakes:

• Thinking TreeMap uses equals() for keys. Correction: key uniqueness is based on comparison result 0, not equals().
• Using TreeMap when order is not needed. Correction: use HashMap for plain key lookup; TreeMap is for sorted access and range queries.
• Forgetting about null-key behavior. Correction: natural-order TreeMap rejects null keys; only a comparator that handles null can allow them.
• Assuming submaps are copies. Correction: they are views backed by the original map, so changes are shared.

Memory Hook: Picture a balanced search tree librarian: every book is placed by alphabet, and after each new book the librarian straightens the shelf so it never leans too far left or right.

Cheat Sheet:

• TreeMap = sorted Map backed by a red-black tree.
• get, put, remove are O(log n).
• Comparator or natural order decides placement.
• Comparison result 0 means same key.
• Great for floor, ceiling, and range views.
• Natural-order TreeMap does not allow null keys.

Practice Tasks:

• Create a TreeMap of exam scores and print the nearest score below and above a target.
• Write a comparator-based TreeMap that sorts strings by length, then test what happens when two strings have the same length.
• Build a subMap view and verify that removing from the view changes the original map.