You've seen how linear structures like arrays and linked lists store data sequentially. But what about data that has a hierarchy? Think of a file system on your computer, with folders inside folders. This is where trees come in.

A tree is a data structure made of nodes connected by edges. It starts at a single top node called the root. Each node can have child nodes, and every node (except the root) has exactly one parent node. Nodes with no children are called leaves.

One of the most common types is the Binary Search Tree (BST). In a BST, every node's left child has a value less than the parent, and every node's right child has a value greater than the parent. This property makes searching very efficient, typically taking $O(\log n)$ time.

However, a BST can become unbalanced if you insert elements in a sorted order. It essentially turns into a linked list, and search time degrades to $O(n)$. To solve this, self-balancing trees like AVL trees and Red-Black trees automatically adjust their structure to maintain the $O(\log n)$ search time, no matter how data is inserted.

If trees represent strict hierarchies, graphs represent networks. Think of a social network, where people are connected to many other people, or a map, where cities are connected by roads. A graph is a set of vertices (nodes) connected by edges.

Unlike trees, graphs can have cycles, and there's no concept of a root or parent-child relationship. We can represent them in a few ways, but the most common for interviews is the adjacency list. It's a map where each key is a vertex, and its value is a list of all vertices it's connected to.

To explore a graph, we use traversal algorithms. The two main ones are:

1. Breadth-First Search (BFS): Explores neighbor nodes first, level by level. It uses a queue and is great for finding the shortest path between two nodes in an unweighted graph.
2. Depth-First Search (DFS): Goes as deep as possible down one path before backtracking. It uses a stack (or recursion) and is useful for detecting cycles or exploring all possibilities, like in a maze.

A Heap is a specialized tree-based structure that keeps track of the greatest or smallest element. It's not for general-purpose searching; it's for priority. A min-heap keeps the smallest element at the root, while a max-heap keeps the largest at the root. This is known as the heap property.

Any time you add or remove an element, the heap reorganizes itself to maintain this property. This makes them perfect for implementing priority queues, where you always need to process the highest-priority item next.

Finally, we have Hash Tables. You might know them as dictionaries, hash maps, or associative arrays. They map keys to values for lightning-fast lookups, inserts, and deletes, all in average $O(1)$ time.

A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. The key is figuring out a good hash function that distributes keys evenly.

But what if two different keys hash to the same index? This is called a collision. The most common way to resolve this is with separate chaining. Each bucket in the array points to a linked list. If a collision occurs, the new key-value pair is simply added to the list at that index.

Time to see how well you've grasped these concepts.

Understanding these advanced structures is key to writing efficient code and solving complex problems. They appear frequently in technical interviews because they reveal how you think about organizing and accessing data.