DSA
Category

Trees and graphs

A tree is a graph with one path between any two nodes. These articles cover that shape, binary search trees, balance, heaps, and the walks that visit every node. They also cover general graphs: adjacency lists, breadth-first and depth-first search, Dijkstra, directed acyclic graphs, and disjoint-set union.

  1. What Is a Tree? Roots, Leaves, and Depth in Nodes

    A tree is a connected, acyclic hierarchy with one root and one parent per non-root node. This course's maxDepth counts nodes on the longest root-to-leaf path: an empty tree is 0 and a single node is 1.

  2. What Is a Binary Search Tree? Left Smaller, Right Larger

    A binary search tree keeps every value in the left subtree smaller than the node and every value in the right subtree larger. This course leaves duplicates out, and search costs the height, not automatically log n.

  3. What Is a Balanced Tree? AVL, Red-Black, and Height

    AVL and red-black trees enforce different invariants with rotations and, for red-black trees, recoloring so height remains O(log n). A skewed BST is a list drawn vertically.

  4. What Is a Binary Heap? Min, Max, and the kth Largest

    A heap is a complete binary tree stored in an array, with the minimum or the maximum at the root. Updating that extreme is O(log n), which is enough to find the kth largest without fully sorting.

  5. How Do Preorder, Inorder, and Postorder Traverse a Tree?

    Depth-first tree traversals differ only in when they visit the current node: preorder before both children, inorder between them, and postorder after them. Inorder lists a binary search tree in sorted order.

  6. What Is a Graph? Vertices, Undirected Edges, and Cycles

    A graph is vertices plus edges. A tree is a graph with no cycles; a general graph can loop, so a search has to remember where it has been. This course uses undirected edges.

  7. What Is an Adjacency List? Neighbours of Each Vertex

    An adjacency list stores, for each vertex, the vertices one edge away. One pass over the edge list builds it, and a search asks it for neighbours.

  8. How Does Breadth-First Search Find the Fewest Edges?

    Breadth-first search uses a queue to walk neighbours, then neighbours of neighbours. When every edge costs the same, the first time you reach a vertex is the fewest edges.

  9. How Does Depth-First Search Explore One Branch First?

    Depth-first search uses a stack or recursion to finish one branch before the others. It answers reachability, not fewest edges.

  10. What Is Dijkstra's Algorithm for Weighted Shortest Paths?

    Enrichment: Dijkstra finds shortest paths when edges have different non-negative costs. A heap always extends the cheapest path so far. The current exercises do not require an implementation.

  11. How Do Directed Cycles and Topological Order Work?

    Enrichment: a directed acyclic graph has a topological order in which every edge points forward. Kahn's algorithm removes zero-indegree vertices; leftovers prove a directed cycle.

  12. What Is Disjoint-Set Union? Tracking Connected Components

    Enrichment: disjoint-set union maintains groups under repeated merges. Path compression and union by size make connectivity checks effectively constant-time across a long sequence.

  13. How Do Heap Indexes Work? Parent and Child Arithmetic

    A binary heap stores a complete tree in an array. The parent and the children of index i are arithmetic, not pointers.

  14. What Is a Visited Set? Stopping a Graph Search from Looping

    A visited set remembers vertices a search has already queued. Without it, a cycle in an undirected graph makes the walk repeat forever.

  15. How Does Insertion Order Determine BST Shape?

    A binary search tree preserves key order but not balance. Insertion order can produce a short tree or a linear spine.