Multiple binary search tree

Question

I need to create multiple trees in order to compare their shape and calculate how many different shapes of trees I got (identical forms will be counted as one form).

Input will be:

trees (how many trees need to be(from 1 to 50) layers (how many nodes will be in 1 tree (from 1 to 20)

values (values in every tree (from 1 to 1000000))

Input with images:

5 3
3 8 2
4 2 5
2 6 10
3 7 6
10 8 4

There must be five trees with three nodes in each. [![enter image description here][1]][1]

The first two trees are the same shape, the others are different.

Output: 4

Example of input:

2 2
1 2 
2 1 

So there must be two trees with two nodes in each.

Answer is 2 because there can be 2 different forms of trees

Another example of input:

6 7
7 6 3 5 4 2 1 
1 3 2 4 7 5 6 
4 7 1 2 5 3 6 
5 1 6 7 2 4 3 
1 3 2 5 6 4 7 
6 7 1 5 4 2 3

Answer: 6

I was able to create one tree with the structure, but I can't figure out how to create several and how to compare their shapes

Maybe I don't need multiple trees. Maybe I'll create one tree, write values to it, then somehow "save" its shape, clear it, and then write the next tree to it.

What would be the best way to do it?

UPD: How can i properly deallocate allocated memory? (i know about free() but i dont know how to use it in this case)

Answer 1

For the compare function :

bool IdenticalTreeShape(struct node *tree1, struct node *tree2)
{
    if (!tree1 && !tree2) {
        return true;
    }
    if (  (!tree1)
        ||(!tree2)
        ||(!IdenticalTreeShape(tree1->left, tree2->left)
        ||(!IdenticalTreeShape(tree1->right, tree2->right) ) {
        return false;
    }
    
    return true;
}

Now, you need to retain every uniq shape you found in order to see if a new proposition would be uniq or not. You can do it in many way.

For example :

Have an array arrayUniq of the number of tree that you will input. Have an integer nbUniq set to 0.

Input and create your tree in arrayUniq[nbUniq]

Compare all tree shape from "0" to "nbUniq - 1" against arrayUniq[nbUniq]. If none tree are identical, increase nbUniq.

Done :)

Answer 2

Pseudo-code (too long for a comment):

bool SameShape(node* tree1, node* tree2)
{
  if (isNull(tree1))
    if isNull(tree2))
      return true;
    else
      return false;
  else
    if (!isNull(tree2))
      return false;
  if (isNull(tree1->left) != isNull(tree2->left))
    return false;
  if (isNull(tree1->right) != isNull(tree2->right))
    return false;
  bool same = true;
  if (!isNull(tree1->left))
    same = SameShape(tree1->left, tree2->left);
  if (same && !isNull(tree1-right)
    same = SameShape(tree1-right, tree2->right);
  return same;
}

}