Trees and Graphs

Trees and Graphs are simple data structures, but have all sorts of Algorithms and problems associated with them. Despite their importance, standard libraries don't usually provide implementations of them.

Trees

Check out Trees, Tree Traversals and Binary Search Trees. Those pages also discuss storing a Tree in an array, which won't usually come up on interviews, but is simple and useful for these challenges. Tree Traversals is a common topic however! Since a Tree is a recursive structure of Nodes, you can use very simple recursive methods to traverse them.

Practice traversing trees by solving these challenges:

• How Tall is the Tree?
• Is it a Search Tree?

Graphs

Graphs are used in a wide variety of problems, but at the minimum, you should know how to do a Depth-First Search (DFS) and Breadth-First Search (BFS). DFS uses recursion (like tree-traversal algorithms), but it tracks visited nodes to avoid getting stuck in a cycle. BFS also tracks visited nodes, but it uses a queue to keep track of what to visit next.

Use DFS or BFS to solve these challenges:

• Connected Components
• Find the Cycles

Graph-style algorithms can also be used when dealing with 2D grids:

• The Greatest Peaks
• Explorer Maze Escape

Advanced Graph Algorithms

Algorithm-focused companies may also expect you to know algorithms for dealing with Weighted Graphs, such as a Shortest Path Algorithm and a Minimum Spanning Tree Algorithm.

Other Stuff to Know

These tree-based data structures are less common on interviews, but still worth reviewing (links are to wikipedia):

• Priority Queues are a specific type of Queue where pop returns the smallest (or largest) item in the Queue. A Heap is an efficient way to implement a Priority Queue in a tree so no operation takes longer than O(log n).
• Tries are useful for storing all prefixes of words in an efficient tree-structure. This is useful for certain applications, such as an auto-complete functionality.
• Balanced Trees are Trees that ensure the longest and shortest branches are approximately the same length, so Algorithms performed on them stay efficient. The most common one is the Red-Black Tree which is a type of Binary Search Tree. The B-Tree is a search tree (non-binary) that is used for accessing blocks of data on slower storage devices such as hard disk drives.