Welcome to Graphs Trees CodeSnap

The 'Graphs & Trees' category delves into non-linear data structures essential for modeling networks, hierarchies, and relationships. Problems range from traversing tree structures (like Inorder, Level Order) and finding properties (Max Depth, LCA, Path Sum) to graph algorithms like detecting cycles, finding connected components (Number of Islands), cloning structures, determining orderings (Topological Sort, Course Schedule, Alien Dictionary), and solving pathfinding challenges (Word Ladder). These problems test understanding of DFS, BFS, recursion, and graph theory fundamentals like connectivity and cycle detection, crucial for complex system modeling and optimization.

Table of Contents

• Binary Tree Inorder Traversal

  Given the root of a binary tree, return the inorder traversal (left node, root node, right node) of its nodes' values. Typically solved recursively or iteratively using a stack.

• Binary Tree Level Order Traversal

  Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level). Requires a queue-based Breadth-First Search (BFS).

• Maximum Depth of Binary Tree

  Given the root of a binary tree, find its maximum depth, which is the number of nodes along the longest path from the root node down to the farthest leaf node. Solvable via recursive DFS or iterative BFS.

• Lowest Common Ancestor of a Binary Tree

  Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The LCA is defined between two nodes p and q as the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).

• Validate Binary Search Tree

  Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST satisfies: the left subtree contains only nodes with keys less than the node's key, the right subtree contains only nodes with keys greater than the node's key, and both subtrees are also BSTs.

• Path Sum

  Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children.

• Number of Islands

  Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are surrounded by water.

• Clone Graph

  Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains an integer val and a list (List[Node]) of its neighbors.

• Course Schedule

  There are n courses labeled 0 to n-1. Some courses have prerequisites, e.g., to take course 0 you have to first take course 1, expressed as pair [0, 1]. Given the total number of courses and prerequisites, return true if you can finish all courses. This is equivalent to detecting cycles in a directed graph.

• Detect Cycle in Undirected Graph

  Given an undirected graph represented typically by an adjacency list or number of vertices and edges, determine if the graph contains a cycle. Can be solved using DFS (tracking parent nodes) or Union-Find.

• Detect Cycle in Directed Graph

  Given a directed graph, check whether the graph contains a cycle. This is often solved using DFS by keeping track of the nodes currently in the recursion stack.

• Topological Sort

  Given a Directed Acyclic Graph (DAG), return a linear ordering of vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. If the graph has cycles, topological sort is not possible. Solvable using Kahn's algorithm (BFS) or DFS.

• Graph Valid Tree

  Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. A graph is a valid tree if it's connected and has no cycles.

• Word Ladder

  Given two words, beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that only one letter can be changed at a time and each transformed word must exist in the word list. Return 0 if no such sequence exists.

• Alien Dictionary

  There is a dictionary of words from an alien language sorted lexicographically by the rules of this language. Derive the order of letters in this language. This involves building a directed graph based on pairwise word comparisons and performing a topological sort.