Forgetting null/base-case handling
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.
Move from brute-force thinking to an efficient approach using tree strategy.
You are given an integer n and an undirected tree with n nodes numbered from 0 to n - 1. The tree is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between ui and vi.
You are also given three distinct target nodes x, y, and z.
For any node u in the tree:
dx be the distance from u to node xdy be the distance from u to node ydz be the distance from u to node zThe node u is called special if the three distances form a Pythagorean Triplet.
Return an integer denoting the number of special nodes in the tree.
A Pythagorean triplet consists of three integers a, b, and c which, when sorted in ascending order, satisfy a2 + b2 = c2.
The distance between two nodes in a tree is the number of edges on the unique path between them.
Example 1:
Input: n = 4, edges = [[0,1],[0,2],[0,3]], x = 1, y = 2, z = 3
Output: 3
Explanation:
For each node, we compute its distances to nodes x = 1, y = 2, and z = 3.
02 + 22 = 22, node 1 is special.02 + 22 = 22, node 2 is special.Therefore, nodes 1, 2, and 3 are special, and the answer is 3.
Example 2:
Input: n = 4, edges = [[0,1],[1,2],[2,3]], x = 0, y = 3, z = 2
Output: 0
Explanation:
For each node, we compute its distances to nodes x = 0, y = 3, and z = 2.
No node satisfies the Pythagorean condition. Therefore, the answer is 0.
Example 3:
Input: n = 4, edges = [[0,1],[1,2],[1,3]], x = 1, y = 3, z = 0
Output: 1
Explanation:
For each node, we compute its distances to nodes x = 1, y = 3, and z = 0.
02 + 12 = 12, node 1 is special.Therefore, the answer is 1.
Constraints:
4 <= n <= 105edges.length == n - 1edges[i] = [ui, vi]0 <= ui, vi, x, y, z <= n - 1x, y, and z are pairwise distinct.edges represent a valid tree.Problem summary: You are given an integer n and an undirected tree with n nodes numbered from 0 to n - 1. The tree is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between ui and vi. You are also given three distinct target nodes x, y, and z. For any node u in the tree: Let dx be the distance from u to node x Let dy be the distance from u to node y Let dz be the distance from u to node z The node u is called special if the three distances form a Pythagorean Triplet. Return an integer denoting the number of special nodes in the tree. A Pythagorean triplet consists of three integers a, b, and c which, when sorted in ascending order, satisfy a2 + b2 = c2. The distance between two nodes in a tree is the number of edges on the unique path between them.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Tree
4 [[0,1],[0,2],[0,3]] 1 2 3
4 [[0,1],[1,2],[2,3]] 0 3 2
4 [[0,1],[1,2],[1,3]] 1 3 0
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3820: Pythagorean Distance Nodes in a Tree
class Solution {
private List<Integer>[] g;
private int n;
private final int inf = Integer.MAX_VALUE / 2;
public int specialNodes(int n, int[][] edges, int x, int y, int z) {
this.n = n;
g = new ArrayList[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (int[] e : edges) {
int u = e[0], v = e[1];
g[u].add(v);
g[v].add(u);
}
int[] d1 = bfs(x);
int[] d2 = bfs(y);
int[] d3 = bfs(z);
int ans = 0;
for (int i = 0; i < n; i++) {
long[] a = new long[] {d1[i], d2[i], d3[i]};
Arrays.sort(a);
if (a[0] * a[0] + a[1] * a[1] == a[2] * a[2]) {
++ans;
}
}
return ans;
}
private int[] bfs(int i) {
int[] dist = new int[n];
Arrays.fill(dist, inf);
Deque<Integer> q = new ArrayDeque<>();
dist[i] = 0;
q.add(i);
while (!q.isEmpty()) {
for (int k = q.size(); k > 0; --k) {
int u = q.poll();
for (int v : g[u]) {
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
q.add(v);
}
}
}
}
return dist;
}
}
// Accepted solution for LeetCode #3820: Pythagorean Distance Nodes in a Tree
func specialNodes(n int, edges [][]int, x int, y int, z int) int {
g := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
const inf = int(1e9)
bfs := func(i int) []int {
dist := make([]int, n)
for k := 0; k < n; k++ {
dist[k] = inf
}
q := make([]int, 0)
dist[i] = 0
q = append(q, i)
for len(q) > 0 {
sz := len(q)
for ; sz > 0; sz-- {
u := q[0]
q = q[1:]
for _, v := range g[u] {
if dist[v] > dist[u]+1 {
dist[v] = dist[u] + 1
q = append(q, v)
}
}
}
}
return dist
}
d1 := bfs(x)
d2 := bfs(y)
d3 := bfs(z)
ans := 0
for i := 0; i < n; i++ {
a := []int{d1[i], d2[i], d3[i]}
sort.Ints(a)
x0, x1, x2 := int64(a[0]), int64(a[1]), int64(a[2])
if x0*x0+x1*x1 == x2*x2 {
ans++
}
}
return ans
}
# Accepted solution for LeetCode #3820: Pythagorean Distance Nodes in a Tree
class Solution:
def specialNodes(
self, n: int, edges: List[List[int]], x: int, y: int, z: int
) -> int:
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
def bfs(i: int) -> List[int]:
q = deque([i])
dist = [inf] * n
dist[i] = 0
while q:
for _ in range(len(q)):
u = q.popleft()
for v in g[u]:
if dist[v] > dist[u] + 1:
dist[v] = dist[u] + 1
q.append(v)
return dist
d1 = bfs(x)
d2 = bfs(y)
d3 = bfs(z)
ans = 0
for a, b, c in zip(d1, d2, d3):
s = a + b + c
a, c = min(a, b, c), max(a, b, c)
b = s - a - c
if a * a + b * b == c * c:
ans += 1
return ans
// Accepted solution for LeetCode #3820: Pythagorean Distance Nodes in a Tree
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3820: Pythagorean Distance Nodes in a Tree
// class Solution {
// private List<Integer>[] g;
// private int n;
// private final int inf = Integer.MAX_VALUE / 2;
//
// public int specialNodes(int n, int[][] edges, int x, int y, int z) {
// this.n = n;
// g = new ArrayList[n];
// Arrays.setAll(g, k -> new ArrayList<>());
// for (int[] e : edges) {
// int u = e[0], v = e[1];
// g[u].add(v);
// g[v].add(u);
// }
//
// int[] d1 = bfs(x);
// int[] d2 = bfs(y);
// int[] d3 = bfs(z);
//
// int ans = 0;
// for (int i = 0; i < n; i++) {
// long[] a = new long[] {d1[i], d2[i], d3[i]};
// Arrays.sort(a);
// if (a[0] * a[0] + a[1] * a[1] == a[2] * a[2]) {
// ++ans;
// }
// }
// return ans;
// }
//
// private int[] bfs(int i) {
// int[] dist = new int[n];
// Arrays.fill(dist, inf);
// Deque<Integer> q = new ArrayDeque<>();
// dist[i] = 0;
// q.add(i);
// while (!q.isEmpty()) {
// for (int k = q.size(); k > 0; --k) {
// int u = q.poll();
// for (int v : g[u]) {
// if (dist[v] > dist[u] + 1) {
// dist[v] = dist[u] + 1;
// q.add(v);
// }
// }
// }
// }
// return dist;
// }
// }
// Accepted solution for LeetCode #3820: Pythagorean Distance Nodes in a Tree
function specialNodes(n: number, edges: number[][], x: number, y: number, z: number): number {
const g: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const inf = 1e9;
const bfs = (i: number): number[] => {
const dist = Array(n).fill(inf);
let q: number[] = [i];
dist[i] = 0;
while (q.length) {
const nq = [];
for (const u of q) {
for (const v of g[u]) {
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1;
nq.push(v);
}
}
}
q = nq;
}
return dist;
};
const d1 = bfs(x);
const d2 = bfs(y);
const d3 = bfs(z);
let ans = 0;
for (let i = 0; i < n; i++) {
const a = [d1[i], d2[i], d3[i]];
a.sort((p, q) => p - q);
if (a[0] * a[0] + a[1] * a[1] === a[2] * a[2]) {
ans++;
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
BFS with a queue visits every node exactly once — O(n) time. The queue may hold an entire level of the tree, which for a complete binary tree is up to n/2 nodes = O(n) space. This is optimal in time but costly in space for wide trees.
Every node is visited exactly once, giving O(n) time. Space depends on tree shape: O(h) for recursive DFS (stack depth = height h), or O(w) for BFS (queue width = widest level). For balanced trees h = log n; for skewed trees h = n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.