I think only SEARCH trees have keys. “Search” means key search. In a search tree (and hashset), each node carries a (usually unique) key + 0 or more data fields as payload.
Insight — Conceptually the key is not part of the payload. Payload implies “additional information”. In contrast, key is part of the search tree (and hashset) infrastructure, similar to auto-increment record IDs in database. In many systems, the key also has natural meaning, unlike auto-incremented IDs.
Insight — If a tree has no payload field, then useful info can only exist in the key. This is fairly common.
For a treemap or hashmap, the key/value pair can be seen as “key+payload”. My re_hash_table_LinearProbing.py implementation saves a key/value pair in each bucket.
A useful graph (including tree , linked list, but not hashset) can have payloads but no search keys. The graph nodes can hold pointers to payload objects on heap . Or The graph nodes can hold Boolean values. Graph construction can be quite flexible and arbitrary. So how do you select a graph node? Just follow some iteration/navigation rules.
Aha — similar situation: linked list has well-defined iterator but no search key . Ditto vector.
 With pre-allocation, a static array substitutes for the heap.
Insight — BST, priorityQ, and hash tables need search key in each item.
I think non-search-TREES are rarely useful. They mostly show up in contrived interview questions. You can run BFT, pre|post-order DFT, but not BF
S / DF S, since there’s nothing to “search”.
Insight — You may say search by payload, but some trees have Boolean payloads.