Given two trees, return true if they are structurally identical they are made of nodes with the same values arranged in the same way

Question

public static boolean identical(treenode<Integer> root1,treenode<Integer> root2)
    {
        boolean ans;
        for(int i=0;i<root1.children.size();i++)
        for(int j=0;j<root2.children.size();j++)
        {
         boolean subans=identical(root1.children.get(i),root2.children.get(j));
         ans=subans;
        }
        if(root1.data==root2.data)
        {
            ans=true;
        }/* what's wrong with the code*/
        else{
            ans=false;
        }
        return ans;
    }/* how can i improve it ? */

i am not able to understand why my code is not working.please tell me the solutions to fix it.

Answer 1

Your for loop is going through every recursive call of identical before evaluating the boolean return of those recursive calls. In other words, you're not evaluating the data of all of the children through your recursive calls. I believe with your code that you may only be evaluating the last child node of every node in the tree (going down the right-most side).

You also have a nested for loop, which is unnecessary in your case.

What I propose is this:

1) Check that the values of your current nodes are the same. If not, or if at least one is null, return false immediately.

2) Check that the sizes of the children are the same for both nodes. If not, return false.

3) Call this recursively with each child node.

This is a depth first, left-side-first search.

Answer 2

private boolean structurallyIdentical(Node tnode, Node onode) {
    if(tnode == null && onode == null) {
        return true;
    }
    if(tnode != null && onode != null) {
        // check that the left branch is identical
        boolean left = structurallyIdentical(tnode.left, onode.left);
        // check that the right branch is identical
        boolean right = structurallyIdentical(tnode.right, onode.right);
        // only identical, if both branches match
        return (left && right);
    }
    return false;
}

Answer 3

A little improvement based on @Vansh Nandwani's answer. SBT = Same Binary Tree

    public  boolean SBT(BinNode root1, BinNode root2)
    {
        if (root1 == null && root2 == null) return true;
        if (root1 != null && root1 != null) {
            if (root1.value() == root2.value())//check if the values are the same 
               {
                boolean left = SBT(root1.left(), root2.left());
                boolean right = SBT(root1.right(), root2.right);
                return (left && right);}
                } 
        return false;
    }

Answer 4

public class Solution {

/*  TreeNode structure 
    class TreeNode<T> {
        T data;
        ArrayList<TreeNode<T>> children;

        TreeNode(T data){
            this.data = data;
            children = new ArrayList<TreeNode<T>>();
        }
    }*/
    
    public static boolean checkIdentical(TreeNode<Integer> root1, TreeNode<Integer> root2){

        if(root1.children.size()!=root2.children.size())
        {
            return false;
        }
         if(root1.children.size()==root2.children.size()){
            if(root1.data==root2.data)
            {
                for(int i=0 ,j=0;i<root1.children.size()&&j<root2.children.size();i++ ,j++){
                    checkIdentical(root1.children.get(i),root2.children.get(j));
                        return true;
                }
            }
        }
        return false;
    }
}

Answer 5

bool areIdentical(TreeNode<int> *root1, TreeNode<int> * root2) 
    {bool ans=false;
    
    
        if(root1->children.size()!=root2->children.size())
        {
            ans =false;
        }
         if(root1->children.size()==root2->children.size()){
            if(root1->data==root2->data)
            {
                for(int j=0;j<root1->children.size();j++){
                    areIdentical(root1->children[j],root2->children[j]);
                    ans=true;
                }
            }
        }
        return ans;
    }

Answer 6

For general tree

Method 1:

bool areIdentical(TreeNode<int> *root1, TreeNode<int> * root2) {
    
    
    if(root1 == NULL && root2 == NULL){
        return true;
    }
    if((root1 == NULL && root2 != NULL) || (root1 != NULL && root2 == NULL)){
        return false;
    }
    if((root1->data != root2->data)|| (root1->children.size() != root2->children.size())){
         return false;
    }
    else if(root1->children.size() == root2->children.size()){
        if(root1->data == root2->data){
           for(int i=0,j=0;i<root1->children.size()&&j<root2->children.size();i++,j++){
                    areIdentical(root1->children[i],root2->children[j]);
                    return true;
           }
        }
    }
    return false;
    
}

//this solution may fail some testcase but Method 2 : work perfectly fine

Method 2 :

bool areIdentical(TreeNode<int> *root1, TreeNode<int> * root2) {
    if(root1 == NULL && root2 == NULL){
        return true;
    }
    if((root1 == NULL && root2 != NULL) || (root1 != NULL && root2 == NULL)){
        return false;
    }
    if((root1->data != root2->data)|| (root1->children.size() != root2->children.size())){
         return false;
    }
    for(int  i = 0;i < root1->children.size();++i){
        TreeNode<int>* child1 = root1->children[i];
        TreeNode<int>* child2 = root2->children[i];
        if(!areIdentical(child1,child2)){
            return false;
        }
    }
    return true;
    
}