Backend Developer
Trees and graphs questions
203 questions on Trees and graphs for backend developers, easiest first.
Easy 61
- Edges in a tree with n nodeseasy
- Most nodes in a binary tree of height 3easy
- What inorder traversal of a BST giveseasy
- Preorder output of a small treeeasy
- Traversal for freeing a whole treeeasy
- Data structure for level-order traversaleasy
- BST search time, typical and worsteasy
- Leaves in a full binary treeeasy
- Recursive maximum depth of a treeeasy
- Child positions in an array-based treeeasy
- Inserting sorted keys into a plain BSTeasy
- What makes a graph a treeeasy
- Call stack depth of recursive traversaleasy
- Finding the smallest key in a BSTeasy
- Complete binary tree meaningeasy
- Space for adjacency list and matrixeasy
- The structure behind BFSeasy
- How DFS remembers where to returneasy
- Fewest hops between two userseasy
- Sum of degrees in an undirected grapheasy
- Edges in a complete grapheasy
- Why traversals track visited nodeseasy
- Running time of BFS with adjacency listseasy
- Counting connected componentseasy
- Neighbours of a cell in a grideasy
- Storing a sparse road networkeasy
- Fast check for one edgeeasy
- Storing weights in an adjacency listeasy
- In-degree in a follower grapheasy
- What a DAG iseasy
- The weight rule for Dijkstraeasy
- Data structure inside Dijkstraeasy
- Shortest paths with refunds as negative costseasy
- Cost of Floyd-Warshalleasy
- What a minimum spanning tree iseasy
- How Kruskal’s algorithm workseasy
- How Prim’s algorithm workseasy
- The two operations of union-findeasy
- What path compression doeseasy
- Why union by size helpseasy
- Dijkstra when every edge costs the sameeasy
- What relaxing an edge meanseasy
- A cycle with negative total costeasy
- Running time of heap-based Dijkstraeasy
- Counting groups after several unionseasy
- Graphs that have a topological ordereasy
- Where Kahn’s algorithm startseasy
- A structure for search-box suggestionseasy
- Cost of a trie lookupeasy
- Courses that require each othereasy
- How build tools order their stepseasy
- More than one valid ordereasy
- Storing children in a trie nodeeasy
- Why a trie node needs an end markereasy
- Which way the dependency edge pointseasy
- Kahn’s algorithm finishes earlyeasy
- When a trie beats a hash seteasy
- What a segment tree is foreasy
- What a Fenwick tree storeseasy
- Nodes in a small trieeasy
- Avoiding loops in graph searcheasy
Medium 82
- Inorder successor with a right subtreemedium
- Deleting a BST node with two childrenmedium
- Bug in a parent-child BST checkmedium
- Traversals that rebuild a unique treemedium
- Inorder traversal without recursionmedium
- Where the tree diameter can bemedium
- Lowest common ancestor in a BSTmedium
- Distinct BSTs with keys 1, 2, 3medium
- Inorder traversal in O(1) extra spacemedium
- Serialising a tree so it can be rebuiltmedium
- Right side view of a binary treemedium
- The AVL balance rulemedium
- Height limit of a red-black treemedium
- Bug in a root-to-leaf path summedium
- K-th smallest key in a BSTmedium
- Checking if a tree is a mirror of itselfmedium
- Checking balance in one passmedium
- Time cost of a full tree traversalmedium
- Why databases index with B-treesmedium
- Finding any key in a binary heapmedium
- When to mark a node as visited in BFSmedium
- Cycle check in an undirected graphmedium
- Cycle check in a directed graphmedium
- When a graph cannot be two-colouredmedium
- Spreading from many starting pointsmedium
- Processing BFS one level at a timemedium
- Shortest grid path around a wallmedium
- Deep-copying a graph with cyclesmedium
- Faster neighbours in word laddermedium
- A JavaScript BFS that gets slowmedium
- Recursive flood fill on a huge gridmedium
- Iterative DFS visiting a different ordermedium
- Flood fill with the same colourmedium
- Capturing regions not touching the bordermedium
- Cells that drain to two oceansmedium
- Edges from undirected adjacency listsmedium
- Checking whether a graph is a treemedium
- Why bidirectional BFS is fastermedium
- BFS on a combination lockmedium
- Finding second-degree connectionsmedium
- Shortest distance in a small road graphmedium
- Old entries left in Dijkstra’s heapmedium
- How Bellman-Ford finds a negative cyclemedium
- Cheapest flight with at most k stopsmedium
- Total weight of a small MSTmedium
- Finding the edge that forms a cyclemedium
- Loop order in Floyd-Warshallmedium
- Shortest paths with 0 and 1 weightsmedium
- Rebuilding the route, not just its costmedium
- Route that avoids the steepest climbmedium
- Time for a signal to reach every servermedium
- When A* is guaranteed optimalmedium
- When the MST is uniquemedium
- Dijkstra on a very dense graphmedium
- Speed of fully optimised union-findmedium
- Merging customer records by emailmedium
- Island count as land is addedmedium
- The heaviest edge on a cyclemedium
- Choosing Prim or Kruskalmedium
- Most reliable path between two serversmedium
- Picking a valid task ordermedium
- Topological order from DFSmedium
- Fewest terms to finish all coursesmedium
- Letter order from a sorted word listmedium
- Saving memory in a large triemedium
- Finding many words on a letter gridmedium
- Longest path in a dependency graphmedium
- Counting routes in a small DAGmedium
- Longest common prefix with a triemedium
- Fast top suggestions per prefixmedium
- Maximum XOR of two numbersmedium
- What a strongly connected component ismedium
- The two passes of Kosarajumedium
- Finding a link whose loss splits the networkmedium
- Routers that are single points of failuremedium
- Array size for a segment treemedium
- Next index in a Fenwick updatemedium
- Alphabetically smallest valid ordermedium
- Telling a user which packages loopmedium
- Shrinking each SCC to one nodemedium
- Cloning a graph with cyclesmedium
- Key for an undirected edgemedium
Hard 60
- Recursive traversal crashes on big inputhard
- Maximum path sum with negative valueshard
- LCA in a tree without BST orderhard
- Counting nodes of a complete tree quicklyhard
- Storing duplicate keys in a BSThard
- When preorder and postorder are not enoughhard
- Worst-case height of an AVL treehard
- Ties in vertical order traversalhard
- Building a balanced BST from sorted datahard
- Answering many LCA queries fasthard
- Binary lifting memory and query costhard
- Flattening a tree into a list in placehard
- Cost of a BST iteratorhard
- Fixing a BST with two swapped keyshard
- Evaluating an expression treehard
- Grid search where keys open doorshard
- Shortest path with k walls you can breakhard
- Edges to finished nodes in directed DFShard
- False cycle alarm in a dependency graphhard
- Adjacency matrix for 100,000 usershard
- BFS over a graph stored in SQLhard
- BFS for a web crawlerhard
- Knight moves across a chessboardhard
- Why use iterative deepeninghard
- Walking every road exactly oncehard
- Visiting every node versus every edgehard
- Is every node reachable from every nodehard
- Island count with diagonal neighbourshard
- Cycle check with duplicate edgeshard
- Visited set for a 5000 × 5000 gridhard
- A graph where Dijkstra goes wronghard
- Making all weights positive by adding a constanthard
- Changing weights without changing the MSThard
- Shortest paths in a DAG with negative edgeshard
- When Dijkstra can stop earlyhard
- Cheapest trip with one half-price couponhard
- Union-find without either optimisationhard
- Connectivity while links are removedhard
- Routers slowly counting uphard
- Fast routes on a country-sized maphard
- All pairs on a sparse graph with negative edgeshard
- Spotting a negative cycle in Floyd-Warshallhard
- Answering division queries with union-findhard
- Connecting 1,000 points by Manhattan distancehard
- All-pairs table for a large cityhard
- Maximum flow in a small networkhard
- Why Edmonds-Karp uses BFShard
- Assigning engineers to on-call shiftshard
- Topological sort on a 200,000-step chainhard
- Checking 2-SAT with strongly connected componentshard
- Range updates on a segment treehard
- Deleting a word from a triehard
- Scanning text for thousands of keywordshard
- Best root for the shortest treehard
- Sum of distances from every nodehard
- Diameter of a tree with two searcheshard
- Kahn’s algorithm hangs on duplicate edgeshard
- How a spreadsheet recalculates cellshard
- Random surfer behind PageRankhard
- Detecting a database deadlockhard