Structural identical tree

#1

I am trying to implement the code with below approach

  1. find out noof nodes at each level in both tree and check is both are same or not if not return false else return true;
    https://ide.codingblocks.com/s/267090
    correct the code if some issue
#2

@Vikaspal this is way too complex, and i am having difficulty in inderstanding your exact logic. There is a much simpler approach.
start from the root node and do any traversal (on both trees). If both nodes are null, return true, if only one of theirs node is null, return false, else continue the traversal.

#3

@Ishitagambhir ya write its turn out to beO(n) just need to find out if any time one root is going to NULL we will return the false.
But I am not able code to my solution even is not best but I still what to code:

  1. suppose we have two tree right, at level 0 both tree has noofnode equal to 1 right means identical
  2. at level 2 one tree 1 has only one node and tree2 has 2 nodes return false.
  3. Even one case would be like this if the height of both the tree is not equal then return false if height is same then check no of nodes at each level
    hope u got my approach
#4

@Vikaspal you cannot tell if a tree is structurally identical just by counting the number of nodes on each level. Eg if I have a tree like

   2
  /
 1

and another tree like

    2
     \
      1

Now according to your algo these would be reported as identical, but they are not.

#5

Also, your approach will be very time consuming because for each node you will check no of nodes at that level, and the height of tree from that node and both these operations will traverse the whole tree, or part of it, again and again.

#6

@Ishitagambhir thanks got i missed that case in my problem:)

1 Like
#7

@Vikaspal please mark your doubt as resolved if you havent already :slight_smile:

1 Like
#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.