Christmas sale is live!

Avail Now
Data Structures and Algorithms

Top 50 DSA Questions on Trees, Graphs, and Dynamic Programming for 2025 Interviews

Preparing for technical interviews in 2025 can feel overwhelming, especially with the emphasis on data structures and algorithms (DSA). Trees, graphs, and dynamic programming remain core topics, appearing in over 70% of FAANG interviews according to recent candidate reports from platforms like LeetCode and Reddit. Whether you’re aiming for roles at Google, Amazon, or Meta, mastering these areas is key to solving real-world problems efficiently. To kickstart your preparation and stay ahead with the latest tips and free resources, sign up for our newsletter and get exclusive access to course updates that can boost your skills.

In this post, we’ll dive deep into the top 50 questions across these topics, drawn from actual interview experiences shared in 2025. We’ll break them down by category, providing problem statements, in-depth explanations, optimal solutions with Python code, time and space complexities, and variations commonly asked. This isn’t just a list—it’s a comprehensive guide with actionable advice to help you practice effectively. As NeetCode’s founder emphasizes, “DSA isn’t about memorizing; it’s about building intuition for real-world problem-solving,” which aligns with trends where interviewers focus on adaptability over rote solutions.

Why Focus on Trees, Graphs, and Dynamic Programming?

These topics test your ability to model complex relationships and optimize computations. Trees are ideal for hierarchical data, like file systems or DOM structures in web development—check out our web development course for more on practical applications. Graphs handle networks, such as social connections or routing algorithms, often seen in system design questions. Dynamic programming (DP) excels at optimization problems, like resource allocation, which is crucial in data science pipelines; explore our data science course to see how DP integrates with ML models.

Statistics from a July 2025 Reddit analysis of over 100 FAANG interviews show graphs appearing in 30% of rounds, trees in 25%, and DP in 20%, with hybrids like DP on trees gaining popularity. Expert Anish De notes, “For anyone learning DSA: it’s not just about interview prep. It’s about sharpening your problem-solving mindset.” To build this, start with easy problems and scale up, using resources like our master DSA, web dev, and system design course.

Top Questions on Trees

Trees are fundamental for interviews, often involving traversal (DFS, BFS) or properties like balance. Here are 17 key questions, with in-depth solutions for the first 10 based on frequency in 2025 reports.

Easy Tree Questions

1. Maximum Depth of Binary Tree

(Problem Statement)
Given the root of a binary tree, return its maximum depth.
This tests recursive thinking. Approach: Use DFS to compute the height as 1 + max(left height, right height). Variation: Minimum depth for unbalanced trees.

				
					Code
def find_missing_repeating(arr, n):
    xor = 0
    for i in range(1, n+1): xor ^= i
    for num in arr: xor ^= num
    set_bit = xor & -xor
    x, y = 0, 0
    for i in range(1, n+1):
        if i & set_bit: x ^= i
        else: y ^= i
    for num in arr:
        if num & set_bit: x ^= num
        else: y ^= num
    return (x, y) if x in arr else (y, x)

Complexity: O(n) time, O(1) space.

				
			

Building Your Portfolio and Resume

A standout resume is key—tailor it to highlight projects and skills.

  • Resume Tips:
    • Quantify achievements: “Optimized algorithm reducing time by 30%.”
    • Include GitHub links.
    • Keep it to one page.

Build 3-5 projects: A chat app, e-commerce site, or ML model.

The Application Process

Start applying in fall 2024 for summer 2025 slots. Use LinkedIn, Handshake, and company career pages.

  • Strategies:
    • Apply to 50+ positions.
    • Network at career fairs.
    • Follow up with recruiters.

According to Inside Higher Ed, computer science majors apply for internships at higher rates than others.

Preparing for Interviews

Interviews typically include coding, behavioral, and sometimes system design.

Behavioral Questions

These assess fit. Common ones from Tech Interview Handbook:

  1. Why do you want to work for this company?
  2. Tell me about a time you faced a challenge in a project.
  3. How do you handle tight deadlines?

Prepare STAR method responses (Situation, Task, Action, Result).

Technical Coding Questions

1. Find Missing and Repeating Element (Easy)

Problem:
Given an array of size n with numbers from 1 to n, one is missing and one repeated. Find both.

Why Asked

Tests array manipulation and math skills. Common in Amazon OAs.

Approach

Use XOR or sum formulas. XOR all elements with 1 to n; result gives missing XOR repeated, then divide.

				
					class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

Time: O(n), Space: O(h) where h is height. Asked in Google interviews for tree balance checks.

				
			

2. Symmetric Tree

Check if a binary tree is a mirror of itself.
Approach: Recursively check if left subtree mirrors right (outer nodes match, inner match). Variation: Check subtree symmetry.

def isSymmetric(root: TreeNode) -> bool:

    def isMirror(left, right):

        if not left and not right:

            return True

        if not left or not right:

            return False

				
					  return (left.val == right.val) and isMirror(left.left, right.right) and isMirror(left.right, right.left)
    return isMirror(root, root)

Time: O(n), Space: O(h). Common in Meta for UI component mirroring.

				
			

3. Binary Tree Level Order Traversal

Return the level order traversal of nodes’ values.
Approach: Use BFS with a queue, processing levels iteratively. Variation: Zigzag traversal.

from collections import deque

				
					def levelOrder(root: TreeNode) -> list[list[int]]:
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

Time: O(n), Space: O(n). Seen in Amazon for hierarchical data processing.

				
			

Medium Tree Questions

4. Lowest Common Ancestor of a Binary Tree

Find the LCA of two nodes.
Approach: DFS to find paths, LCA is deepest common node. Optimized: Recursive search.

				
					 Approach: DFS to find paths, LCA is deepest common node. Optimized: Recursive search.
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right

Time: O(n), Space: O(h). Frequent in Microsoft for file system queries.

				
			
  • 5. Diameter of Binary Tree

    Return the length of the longest path.

				
					 Approach: DFS computing height, diameter = max(left + right heights).
def diameterOfBinaryTree(root: TreeNode) -> int:
    def height(node):
        nonlocal diameter
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        diameter = max(diameter, left + right)
        return 1 + max(left, right)
    diameter = 0
    height(root)
    return diameter

Time: O(n), Space: O(h). Asked in Netflix for network optimization.

				
			
  • 6. Invert Binary Tree

    Flip the tree left-right.
    Approach: Recursive swap of left/right children.

				
					def invertTree(root: TreeNode) -> TreeNode:
    if root:
        root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

Time: O(n), Space: O(h). Basic for Apple UI flips.

				
			
  • 7. Validate Binary Search Tree

    Check if it’s a valid BST.
    Approach: In-order traversal should be sorted, or recursive bounds check.

				
					def isValidBST(root: TreeNode) -> bool:
    def validate(node, low=float('-inf'), high=float('inf')):
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return validate(node.left, low, node.val) and validate(node.right, node.val, high)
    return validate(root)

Time: O(n), Space: O(h). Core for Google search efficiency.

				
			
  • 8. Path Sum

    Check if there’s a root-to-leaf path summing to target.
    Approach: Recursive subtract from target.

				
					def hasPathSum(root: TreeNode, targetSum: int) -> bool:
    if not root:
        return False
    if not root.left and not root.right:
        return targetSum == root.val
    return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)

Time: O(n), Space: O(h). Variation: All paths.

				
			

9. Construct Binary Tree from Preorder and Inorder Traversal

Build the tree.
Approach: Preorder first is root, inorder splits left/right.

				
					def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode:
    if not preorder or not inorder:
        return None
    root = TreeNode(preorder[0])
    mid = inorder.index(preorder[0])
    root.left = buildTree(preorder[1:mid+1], inorder[:mid])
    root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
    return root

Time: O(n), Space: O(n). Asked in Adobe for parsing.

				
			
  1. 10. Binary Tree Maximum Path Sum

    Find max path sum any node to any node.

				
					def maxPathSum(root: TreeNode) -> int:
    def max_gain(node):
        nonlocal max_sum
        if not node:
            return 0
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)
        price_newpath = node.val + left_gain + right_gain
        max_sum = max(max_sum, price_newpath)
        return node.val + max(left_gain, right_gain)
    max_sum = float('-inf')
    max_gain(root)
    return max_sum

Time: O(n), Space: O(h). High-frequency in Amazon.

				
			

Additional Tree Questions (Brief):
11. Serialize and Deserialize Binary Tree
12. Sum of Left Leaves
13. Binary Tree Paths
14. Kth Smallest Element in BST
15. Bottom View of Binary Tree
16. Vertical Order Traversal
17. Leaf-Similar Trees

Top Questions on Graphs

Graphs model connections, with BFS/DFS for traversal and Union-Find for cycles. Here’s 17 questions, detailed for 10.

Easy Graph Questions

1. Number of Islands

				
					Count islands (connected 1's) in a grid.
 Approach: DFS/BFS to mark visited, count starts.
def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visit = set()
    islands = 0

    def bfs(r, c):
        q = deque([(r, c)])
        while q:
            row, col = q.popleft()
            directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1' and (nr, nc) not in visit):
                    q.append((nr, nc))
                    visit.add((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visit:
                bfs(r, c)
                islands += 1
    return islands

Time: O(mn), Space: O(mn). Apple ML segmentation.

				
			

2. Clone Graph

Deep copy a graph.
Approach: BFS with map for visited/cloned nodes.

				
					class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node: Node) -> Node:
    if not node:
        return node
    visit = {}
    q = deque([node])
    visit[node] = Node(node.val, [])
    while q:
        n = q.popleft()
        for neighbor in n.neighbors:
            if neighbor not in visit:
                visit[neighbor] = Node(neighbor.val, [])
                q.append(neighbor)
            visit[n].neighbors.append(visit[neighbor])
    return visit[node]

Time: O(n), Space: O(n). Meta social graphs.
 
				
			

3. Graph Valid Tree

Check if n nodes form a tree (no cycles, connected).
Approach: Union-Find for cycle detection, ensure one component.

				
					 Time: O(n), Space: O(n).

				
			

Medium Graph Questions

4. Course Schedule

Detect if courses can be finished (cycle detection).
Approach: Topological sort with indegrees or DFS.

from collections import defaultdict



				
					def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    indegree = [0] * numCourses
    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1
    q = deque([i for i in range(numCourses) if indegree[i] == 0])
    count = 0
    while q:
        node = q.popleft()
        count += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
    return count == numCourses

Time: O(n + e), Space: O(n + e). Uber task scheduling.

				
			

5. Pacific Atlantic Water Flow

Find cells where water flows to both oceans.
Approach: BFS from oceans, find intersection

				
					 Time: O(mn), Space: O(mn).

				
			

6. Rotting Oranges

Time for all oranges to rot.
Approach: BFS from rotten, count minutes

				
					def orangesRotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    time = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                fresh += 1
            if grid[r][c] == 2:
                q.append((r, c))
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    while q and fresh > 0:
        for i in range(len(q)):
            r, c = q.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1):
                    grid[nr][nc] = 2
                    q.append((nr, nc))
                    fresh -= 1
        time += 1
    return time if fresh == 0 else -1

Time: O(mn), Space: O(mn). Amazon logistics.

				
			

7. Alien Dictionary

Find order of characters from words.
Approach: Build graph from word pairs, topological sort.
Time: O(c), where c is total characters.

8. Number of Connected Components

Count components in undirected graph.
Approach: Union-Find or DFS.
Time: O(n).

9. Word Search

Find if word exists in grid.
Approach: DFS with backtracking.

				
					def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    path = set()

    def dfs(r, c, i):
        if i == len(word):
            return True
        if (r < 0 or c < 0 or r >= rows or c >= cols or word[i] != board[r][c] or (r, c) in path):
            return False
        path.add((r, c))
        res = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        path.remove((r, c))
        return res

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

Time: O(mn4^l), Space: O(l) where l is word length.

				
			

10. Shortest Path in Binary Matrix

Find shortest path from top-left to bottom-right.
Approach: BFS.
Time: O(m*n).

Additional Graph Questions:
11. Longest Consecutive Sequence
12. Pacific Atlantic Water Flow (detailed above)
13. Minimum Knight Moves
14. Find if Path Exists in Graph
15. Reconstruct Itinerary
16. Cheapest Flights Within K Stops
17. Network Delay Time

Top Questions on Dynamic Programming

DP optimizes by storing subproblem results. Here’s 16 questions, detailed for 10.

Easy DP Questions

1. Climbing Stairs

				
					Ways to climb n stairs (1 or 2 steps).
 Approach: DP[i] = DP[i-1] + DP[i-2].
def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Time: O(n), Space: O(n). Optimized to O(1) space. Microsoft basics.

				
			

2. House Robber

Max amount without robbing adjacent houses.

				
					 Approach: DP[i] = max(DP[i-1], DP[i-2] + nums[i]).
def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    n = len(nums)
    if n <= 2:
        return max(nums)
    dp = [0] * n
    dp[0], dp[1] = nums[0], max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

Time: O(n), Space: O(n). Amazon optimization.

				
			

3. Fibonacci Number

Compute nth Fibonacci.
Approach: Bottom-up DP.
Time: O(n).

Medium DP Questions

4. Longest Increasing Subsequence

Find length of LIS.

				
					 Approach: DP[i] = max(DP[j] + 1 for j < i if nums[j] < nums[i]). Optimized with binary search O(n log n).
def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Time: O(n^2), Space: O(n).

				
			

5. Coin Change

Fewest coins to make amount.

				
					Approach: DP[amount] = min(DP[amount - coin] + 1).
def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Time: O(a * c), Space: O(a).

				
			

6. Unique Paths

Ways to reach bottom-right in grid.

				
					 Approach: DP[i][j] = DP[i-1][j] + DP[i][j-1].
def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[-1][-1]

Time: O(mn), Space: O(mn).

				
			

7. Longest Common Subsequence

LCS of two strings.

				
					 Approach: 2D DP, if match DP[i][j] = DP[i-1][j-1] + 1 else max.
def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Time: O(mn), Space: O(mn).

				
			

8. Word Break

If string can be segmented into dictionary words.

				
					
 Approach: DP[i] = True if DP[j] and s[j:i] in dict.
def wordBreak(s: str, wordDict: list[str]) -> bool:
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

Time: O(n^2), Space: O(n).

				
			

9. Maximum Product Subarray

Max product of contiguous subarray.
Approach: Track max/min products due to negatives.

				
					def maxProduct(nums: list[int]) -> int:
    if not nums:
        return 0
    max_prod = min_prod = result = nums[0]
    for num in nums[1:]:
        temp = max_prod
        max_prod = max(num, max_prod * num, min_prod * num)
        min_prod = min(num, temp * num, min_prod * num)
        result = max(result, max_prod)
    return result

Time: O(n), Space: O(1).

				
			

10. Edit Distance

Min operations to convert word1 to word2.
Approach: 2D DP for insert/delete/replace.

				
					def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    return dp[m][n]

Time: O(mn), Space: O(mn). Google text processing.

				
			
  1. Additional DP Questions:
    11. Decode Ways
    12. Jump Game
    13. Partition Equal Subset Sum
    14. Longest Palindromic Substring
    15. 0/1 Knapsack
    16. Minimum Path Sum

    Preparation Tips and Strategies

    To ace these in 2025, practice on LeetCode (aim for 200+ problems) and analyze patterns like recursion with memoization for trees/DP hybrids. Use our DSA course for structured learning or the crash course for quick refreshers. Track progress with a table:

    Topic

    Questions Solved

    Weak Areas

    Next Steps

    Trees

    15/17

    Diameter variations

    Practice hybrids with DP

    Graphs

    12/17

    Topological sort

    Focus on BFS optimizations

    DP

    14/16

    2D DP

    Apply to strings/arrays

    Review mistakes, optimize code, and mock interview. As per a LinkedIn expert, “Prepare only trees, DP, graphs for this FAANG company? No—master fundamentals for all.”

    Conclusion

    Mastering these 50 questions will equip you for 2025 interviews, where adaptability shines. Start practicing today—consistency is key. For more, enroll in our courses and transform your career. What’s your toughest DSA topic? Share in the comments!

    FAQs

What are the most common tree questions in 2025 interviews?

  1.  Common ones include maximum depth, symmetric tree, and LCA, focusing on traversal and properties.

  1.  Use BFS for shortest paths, DFS for connectivity, and Union-Find for cycles in undirected graphs.

What dynamic programming patterns are essential for FAANG?

  1.  Key patterns: 0/1 knapsack, longest increasing subsequence, and house robber for optimization.

    1.  Aim for 200-300, emphasizing trees, graphs, DP, arrays, and strings for balanced prep.

DSA, High & Low Level System Designs

Buy for 52% OFF
₹25,000.00 ₹11,999.00

Accelerate your Path to a Product based Career

Boost your career or get hired at top product-based companies by joining our expertly crafted courses. Gain practical skills and real-world knowledge to help you succeed.

Reach Out Now

If you have any queries, please fill out this form. We will surely reach out to you.

Contact Email

Reach us at the following email address.

arun@getsdeready.com

Phone Number

You can reach us by phone as well.

+91-97737 28034

Our Location

Rohini, Sector-3, Delhi-110085

WhatsApp Icon

Master Your Interviews with Our Free Roadmap!

Hi Instagram Fam!
Get a FREE Cheat Sheet on System Design.

Hi LinkedIn Fam!
Get a FREE Cheat Sheet on System Design

Loved Our YouTube Videos? Get a FREE Cheat Sheet on System Design.