Count Valid Paths in a Tree - Video Solutions

HardMathDynamic ProgrammingTreeDepth-First SearchNumber Theory

Validate Binary Search Tree - Depth First Search - Leetcode 98

9:56257,702 views

10 video solutions available

Count Valid Paths in a Tree - Video Solution

Watch 10 video solutions for Count Valid Paths in a Tree, a hard level problem involving Math, Dynamic Programming, Tree. This walkthrough by NeetCode has 257,702 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.

Problem Statement

There is an undirected tree with n nodes labeled from 1 to n. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the tree.

Return the number of valid paths in the tree.

A path (a, b) is valid if there exists exactly one prime number among the node labels in the path from a to b.

Note that:

The path (a, b) is a sequence of distinct nodes starting with node a and ending with node b such that every two adjacent nodes in the sequence share an edge in the tree.
Path (a, b) and path (b, a) are considered the same and counted only once.

Example 1:

Input: n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]
Output: 4
Explanation: The pairs with exactly one prime number on the path between them are: 
- (1, 2) since the path from 1 to 2 contains prime number 2. 
- (1, 3) since the path from 1 to 3 contains prime number 3.
- (1, 4) since the path from 1 to 4 contains prime number 2.
- (2, 4) since the path from 2 to 4 contains prime number 2.
It can be shown that there are only 4 valid paths.

Example 2:

Input: n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]
Output: 6
Explanation: The pairs with exactly one prime number on the path between them are: 
- (1, 2) since the path from 1 to 2 contains prime number 2.
- (1, 3) since the path from 1 to 3 contains prime number 3.
- (1, 4) since the path from 1 to 4 contains prime number 2.
- (1, 6) since the path from 1 to 6 contains prime number 3.
- (2, 4) since the path from 2 to 4 contains prime number 2.
- (3, 6) since the path from 3 to 6 contains prime number 3.
It can be shown that there are only 6 valid paths.

Constraints:

1 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
1 <= u_i, v_i <= n
The input is generated such that edges represent a valid tree.

Read full problem with examples

Continue Learning

Practice this problem

Solve it on FleetCode

Read Solution & Explanation

Detailed text walkthrough

Count Valid Paths in a Tree - Video Solutions

Validate Binary Search Tree - Depth First Search - Leetcode 98

Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python

Graph Valid Tree - Leetcode 261 - Python

Microsoft's Most Asked Question 2021 - Count Good Nodes in a Binary Tree - Leetcode 1448 - Python

Path Sum - Leetcode 112 - Python

Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree | Day 30 LeetCode

Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree | leetcode

2867. Count Valid Paths in a Tree | Weekly Leetcode 364

2791. Count Paths That Can Form a Palindrome in a Tree | O(N^3) - O(N*N) - O(N) |Leetcode Weekly 355

Leetcode Weekly contest 355 - Hard - Count Paths That Can Form a Palindrome in a Tree

Count Valid Paths in a Tree - Video Solution

Problem Statement

Continue Learning

Count Valid Paths in a Tree - Video Solutions

Validate Binary Search Tree - Depth First Search - Leetcode 98

Binary Tree Maximum Path Sum - DFS - Leetcode 124 - Python

Graph Valid Tree - Leetcode 261 - Python

Microsoft's Most Asked Question 2021 - Count Good Nodes in a Binary Tree - Leetcode 1448 - Python

Path Sum - Leetcode 112 - Python

Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree | Day 30 LeetCode

Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree | leetcode

2867. Count Valid Paths in a Tree | Weekly Leetcode 364

2791. Count Paths That Can Form a Palindrome in a Tree | O(N^3) - O(N*N) - O(N) |Leetcode Weekly 355

Leetcode Weekly contest 355 - Hard - Count Paths That Can Form a Palindrome in a Tree

Count Valid Paths in a Tree - Video Solution

Problem Statement

Continue Learning