LeetCode 1612: Check If Two Expression Trees are Equivalent Solution

Master LeetCode problem 1612 (Check If Two Expression Trees are Equivalent), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1612. Check If Two Expression Trees are Equivalent

Medium

Hash Table Tree Depth-First Search Binary Tree Counting

Problem Explanation

Explanation:

To check if two expression trees are equivalent, we need to compare their structures as well as the values of the nodes. We can perform a recursive traversal of the trees and compare the nodes at each step. If the nodes are both operators, we compare their values and recursively check their left and right children. If the nodes are operands, we simply compare their values. If the structures and values of the trees match, the trees are considered equivalent.

Algorithm:

Implement a recursive function that takes two nodes as input and checks if they are equivalent.
If both nodes are operators, compare their values and recursively check their left and right children.
If both nodes are operands, compare their values.
If the structures and values of the nodes match recursively, the trees are considered equivalent.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the expression trees.

Space Complexity:

The space complexity of this algorithm is O(h), where h is the height of the expression trees.

Solution Code

// Java Solution
class Solution {
    public boolean checkEquivalence(Node root1, Node root2) {
        Map<Character, Integer> map = new HashMap<>();
        updateMap(root1, map, 1);
        updateMap(root2, map, -1);
        for (int count : map.values()) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
    
    private void updateMap(Node node, Map<Character, Integer> map, int value) {
        if (node == null) {
            return;
        }
        if (node.val != '+') {
            map.put(node.val, map.getOrDefault(node.val, 0) + value);
        }
        updateMap(node.left, map, value);
        updateMap(node.right, map, value);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1612 (Check If Two Expression Trees are Equivalent)?

This page provides optimized solutions for LeetCode problem 1612 (Check If Two Expression Trees are Equivalent) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1612 (Check If Two Expression Trees are Equivalent)?

The time complexity for LeetCode 1612 (Check If Two Expression Trees are Equivalent) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1612 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1612 in Java, C++, or Python.

Back to LeetCode Solutions