Checks — leaves at same level, duplicate subtrees, is-a-tree (graph), min swaps to BST
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
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").