Practice › Trees
Identical Trees
Easy · Trees · Asked at Amazon, Microsoft, Bloomberg
Print YES if the two binary trees have exactly the same structure and the same values, otherwise NO.
Input
The first tree (a line with k, then a line with its level order, -1 = no node), followed by the second tree in the same format.
Output
YES or NO.
Constraints
- 1 ≤ nodes in each tree ≤ 10^4
Recursively: both empty → same; one empty → different; otherwise compare values and both subtrees.
Example 1
Input
3 1 2 3 3 1 2 3
Output
YES
Example 2
Input
2 1 2 3 1 -1 2
Output
NO
Hints
- Two empty trees are identical; an empty and a non-empty one are not.
- Otherwise the roots must have equal values and both pairs of subtrees must be identical.
Approach
same(a, b): if either is null, return whether both are; else return a.val == b.val && same(a.left, b.left) && same(a.right, b.right). Each node pair is compared once.
Complexity: O(n) time · O(h) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
bool same(Node *a, Node *b) {
if (!a || !b) return a == b;
return a->val == b->val && same(a->left, b->left) && same(a->right, b->right);
}
int main() {
Node *a = readTree();
Node *b = readTree();
cout << (same(a, b) ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def build_tree(v):
"""Build a tree from level order where -1 means "no node"."""
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < len(v):
cur = q.popleft()
if i < len(v) and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < len(v) and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]
b = build_tree(rest[1 : 1 + rest[0]])
def same(x, y):
if not x or not y:
return x is y
return x.val == y.val and same(x.left, y.left) and same(x.right, y.right)
print("YES" if same(root, b) else "NO")Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
static boolean same(Node a, Node b) {
if (a == null || b == null) return a == b;
return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Node a = readTree(sc), b = readTree(sc);
System.out.println(same(a, b) ? "YES" : "NO");
}
}