Even though linked lists may be the most popular data structure for interview, trees are a close second. A tree is a structure where each element has some number of child nodes. A binary tree is a special kind where each element has at most two children. A further specialization is the binary search tree. Nodes on the left are less, while nodes on the right are greater.A balanced tree has the same number of nodes on the left and right child subtrees. This makes for an optimal search if it is a binary search tree. If a tree gets too unbalanced, it starts to behave like a linked list (which has worse search performance).
If you get a question at an interview on trees, try to think about recursively solving the problem. Here are some more tree facts. Traversing the tree means to visit all the nodes in the tree. And a heap is a binary tree whereby each node has a value less its parent node.
Next time I will briefly mention graphs. Then I will cover arrays.
