Summary

Trees and graphs are commonly used data structures for an interview, especially trees. Both data structures consist of nodes that reference other nodes in the structure. A tree is actually a special case of a graph, one that doesn’t contain any cycles.

The three major kinds of trees are the binary tree, the binary search tree, and the heap. A binary tree has left and right children. A binary search tree is a binary tree that orders itself so that all the nodes to the left of a node have values less than or equal to the node’s own value and all nodes to the right of a node have values greater than or equal to the node’s value. A heap is a tree in which each node’s children have values less than or equal to the node’s value, which means the heap can be searched in linear time.

Although you should understand the differences between the tree types, most interview problems focus on binary tree operations such as tree traversal.