Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Two empty trees are identical; an empty and a non-empty one are not.
  2. 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");
    }
}

Solve Identical Trees online · All practice problems