How to check mirror in N-ary tree using hashing in Java

In computer science and data structures, trees are the basic structures that depict hierarchical data. A very interesting problem about trees is verifying if two N-ary treesAn N-ary tree is a tree data structure where a node can have up to N children. are its mirrors. This includes checking if one tree is the exact duplicate of the other.

Understanding and solving the problem of checking mirrors in N-ary trees has several real-world applications and benefits. Here are some domains where this problem is relevant:

Network topology and design: In network design, it is essential to understand the symmetry and redundancy of network structures. Ensuring that network topologies are mirrored can provide insights into load balancing and fault tolerance.
User interface design: When creating user interfaces that need to mirror layouts for different orientations or localizations, checking the mirrored structure programmatically can ensure consistency and correctness in the design.
Robotics and path planning: In robotics, mirrored tree structures can be used to plan symmetric paths or to verify that two paths are symmetric, which is useful in synchronized robot movements.
Data synchronization: Ensuring that mirrored data structures are consistent across different systems is crucial for data integrity in distributed systems and cloud computing.
Genetic research: In bioinformatics, tree structures are used to show the phylogenetic treesA phylogenetic tree is a graphical representation of the evolutionary relationships between biological entities, usually sequences or species. . Mirroring trees can be used by evolutionists in order to study the evolution of species.

What is a mirror in N-ary trees?

Two N-ary trees are considered mirrors of each other if they exhibit the following properties:

The root nodes are the same (or equivalent).
The children of each node in one tree are in the reverse order of the children in the corresponding node in the other tree.

Note: The tree structure and the values should mirror each other, node for node (each node in one tree should have a corresponding node in the other tree at the same level, but in reverse order), in both trees.

For the above two N-ary trees, we have the edges as:

N-ary tree $1$ edge $1$ : $7 \rightarrow 8$
N-ary tree $1$ edge $2$ : $7 \rightarrow 9$
N-ary tree $2$ edge $1$ : $7 \rightarrow 9$
N-ary tree $2$ edge $2$ : $7 \rightarrow 8$

Since the roots of both trees are the same and the children of each node in ‘N-ary tree $1$ ’ is in the reverse order of the children in the corresponding node in the ‘N-ary tree $2$ ’, thus both trees are mirrors of each other.

Hashing to check mirroring

Hashing is a technique that maps data to a fixed-size output, which can be used to compare complex structures quickly. To check if two N-ary trees are mirrors, we can hash the structure and values of each tree and compare the results.

The following steps outline our approach:

Hash the tree structure: Traverse the tree and generate a hash based on the structure and values of each node.
Check the mirror property: Determine if the hashed values of two trees indicate that they are mirrors of each other.
Handle children’s order: Ensure that the order of children in one tree is the reverse of the other.

Let’s understand this process with the help of an illustration:

MirrorChecker.java

TreeNode.java

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class MirrorChecker {
    // Hash a tree to create a unique representation
    private static String hashTree(TreeNode node, boolean reverseOrder) {
        if (node == null) {
            return "";
        }
        // Start the hash with the node's value
        StringBuilder hashBuilder = new StringBuilder();
        hashBuilder.append(node.value);
        // Create a list to store the hashes of the children
        List<String> childrenHashes = new ArrayList<>();
        for (TreeNode child : node.children) {
            childrenHashes.add(hashTree(child, reverseOrder));
        }
        // Sort or reverse the order of the children hashes based on the 'reverseOrder' flag
        if (reverseOrder) {
            Collections.reverse(childrenHashes);
        } else {
            Collections.sort(childrenHashes);
        }
        // Append the sorted/reversed hashes to the main hash
        for (String childHash : childrenHashes) {
            hashBuilder.append("-").append(childHash);
        }
        return hashBuilder.toString();
    }
    // Check if two trees are mirrors by comparing their hashes
    public static boolean areMirrors(TreeNode tree1, TreeNode tree2) {
        // Get the hash for the first tree with normal order
        String hash1 = hashTree(tree1, false);
        // Get the hash for the second tree with reversed order
        String hash2 = hashTree(tree2, true);
        return hash1.equals(hash2);
    }
    public static void main(String[] args) {
        // Create the first tree
        TreeNode root1 = new TreeNode(1);
        TreeNode child11 = new TreeNode(2);
        TreeNode child12 = new TreeNode(3);
        root1.addChild(child11);
        root1.addChild(child12);
        // Create the second tree (mirror of the first)
        TreeNode root2 = new TreeNode(1);
        TreeNode child21 = new TreeNode(3);
        TreeNode child22 = new TreeNode(2);
        root2.addChild(child21);
        root2.addChild(child22);
        // Check if the trees are mirrors
        boolean isMirror = areMirrors(root1, root2);
        System.out.println("Are the trees mirrors? " + isMirror); // Expected output: true
    }
}

Code explanation of `MirrorChecker.java` file

Let’s look at the breakdown of the MirrorChecker.java file below:

Lines 1–3: Imports List, ArrayList, and Collections. Collections is used for sorting and reversing lists, while List and ArrayList are used to represent N-ary tree structures.
Lines 7–36: Implements a method hashTree that generates a hash representation of N-ary tree node. The reverseOrder parameter determines if the children should be hashed in reverse order.
- Lines 8–10: Checks if the node is null. If so, returns an empty string, indicating no more nodes to process.
- Lines 13–14: Initializes a StringBuilder and appends the node’s value to start building the hash.
- Line 17: Creates a list childrenHashes to store the hash representations of the children nodes.
- Lines 19–21: Iterates over the children list and recursively calls hashTree, adding each result to childrenHashes.
- Lines 24–28: If reverseOrder is true, reverses childrenHashes. Otherwise, sorts it to maintain consistent ordering.
- Lines 31–33: Appends each hash from childrenHashes to hashBuilder, forming the complete hash representation.
Lines 39–47: Implements the areMirrors method, which checks if two N-ary trees are mirrors of each other by comparing their hash representations.
- Lines 41–44: Gets the hash for the first tree in normal order and for the second tree in reverse order.
- Line 46: Returns the result of the comparison after comparing the two hash values. If they are equal, the trees are considered mirrors.
Lines 59–67: The main method creates two trees and checks if they are mirrors of each other, using the areMirrors method to determine if the hash representations indicate mirroring.
- Lines 51–55: Creates the first tree with a root node of 1 and child nodes 2 and 3.
- Lines 58–62: Creates the second tree with a root node of 1, but with child nodes in reverse order: 3 and 2.
- Line 65: Calls areMirrors method to check if these two trees are mirrors and stores the result in variable isMirror.
- Line 66: Outputs whether the trees are mirrors. If areMirrors returns true, the output will be “Are the trees mirrors? true.”

Code explanation of `TreeNode.java` file

Let’s look at the breakdown of the TreeNode.java file below:

Lines 1–2: Imports the List and ArrayList classes from the java.util package, allowing the creation of lists to manage children nodes in the N-ary tree.
Lines 4–16:
- Defines a class TreeNode representing a node in N-ary tree.
- The class has two fields: value (an integer representing the node’s data) and children (a list to store references to child nodes).
Lines 8–15:
- Line 8: Constructor for TreeNode that initializes the value with the given argument and creates an empty list for children.
- Line 10: Initializes the children list with a new ArrayList.
- Lines 13–15: Here, we have a method addChild that adds a given TreeNode to the children list.

Quiz

Let’s challenge your understanding of this Answer. This will help you assess how well you’ve grasped the key concepts we’ve discussed.

What is the purpose of hashing the N-ary tree in the hashTree method of the MirrorChecker class?

private static String hashTree(TreeNode node, boolean reverseOrder) {
        if (node == null) {
            return "";
        }

        StringBuilder hashBuilder = new StringBuilder();
        hashBuilder.append(node.value);

        List<String> childrenHashes = new ArrayList<>();

        for (TreeNode child : node.children) {
            childrenHashes.add(hashTree(child, reverseOrder));
        }

        if (reverseOrder) {
            Collections.reverse(childrenHashes);
        } else {
            Collections.sort(childrenHashes);
        }

        for (String childHash : childrenHashes) {
            hashBuilder.append("-").append(childHash);
        }

        return hashBuilder.toString();
    }

To store the tree in a compressed format

To ensure the uniqueness of the tree’s representation

To encrypt the tree data for security purposes

To improve the performance of tree traversal operations

Question 1 of 20 attempted

Free Resources

How to check mirror in N-ary tree using hashing in Java

What is a mirror in N-ary trees?

Hashing to check mirroring

Implementation

Code explanation of MirrorChecker.java file

Code explanation of TreeNode.java file

Quiz

Code explanation of `MirrorChecker.java` file

Code explanation of `TreeNode.java` file