Checks — leaves at same level, duplicate subtrees, is-a-tree (graph), min swaps to BST

Medium

Problem

Four checks:

All leaves at the same level? Does the tree contain two identical subtrees with 2 or more nodes (find all duplicate subtrees)? Is an undirected graph a tree — connected, with no cycle? Minimum swaps to turn a complete binary tree (given as an array) into a BST — this is the minimum number of swaps to sort its in-order sequence.

Example 1

Input:  min swaps: [5, 6, 7, 8, 9, 10, 11]
Output: 3

In-order is [8, 6, 9, 5, 10, 7, 11]; sorting it takes 3 swaps.

Also asked as: Check if all leaf nodes are at same level or not · Check if a Binary Tree contains duplicate subtrees of size 2 or more · Find all Duplicate subtrees in a Binary tree · Check if given graph is tree or not · Find minimum swaps required to convert a Binary tree into BST

Test cases

Case 1

Input:    [1,2,3]
Expected: true

Case 2

Input:    [1,2,3,4]
Expected: false

Case 3

Input:    [1,2,null,3]
Expected: true

Case 4

Input:    [1]
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution3 approaches

1. All leaves at the same level

Time O(n)Space O(h)

DFS tracking depth; record the first leaf’s depth and require every other leaf to match.

function leavesSameLevel(root) {
let leafDepth = -1;
const dfs = (n, d) => {
if (!n) return true;
if (!n.left && !n.right) {
if (leafDepth === -1) leafDepth = d;
return d === leafDepth;
}
return dfs(n.left, d + 1) && dfs(n.right, d + 1);
};
return dfs(root, 0);
}

2. Duplicate subtrees — serialize and count

Time O(n²) worst (string sizes), O(n) with idsSpace O(n)

Post-order serialize each subtree to a string; the first time a serialization repeats, that subtree is a duplicate.

function findDuplicateSubtrees(root) {
const seen = new Map(), res = [];
const ser = (n) => {
if (!n) return '#';
const s = n.val + ',' + ser(n.left) + ',' + ser(n.right);
seen.set(s, (seen.get(s) || 0) + 1);
if (seen.get(s) === 2) res.push(n);
return s;
};
ser(root);
return res;
}

3. Is an undirected graph a tree?

Time O(V + E)Space O(V + E)

A graph with n nodes is a tree iff it has exactly n−1 edges and is connected (one DFS/BFS component, no back-edge to a non-parent).

function isGraphTree(n, edges) {
if (edges.length !== n - 1) return false;
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
const seen = new Array(n).fill(false);
const stack = [0];
seen[0] = true;
let count = 1;
while (stack.length) {
const u = stack.pop();
for (const v of adj[u]) if (!seen[v]) { seen[v] = true; count++; stack.push(v); }
}
return count === n;
}

Min swaps to convert a binary tree to a BST: take the tree’s inorder array, then count minimum swaps to sort it (cycle decomposition — see "Minimum swaps to sort an array").