Search code examples
pythonalgorithmtreebinary-tree

How to describe and code an algorithm to check if two binary trees are identical or not?

Their quality standards require me to use proper grammar and write what I have already tried but I have really no information. It just asks me to do that and I have no idea how to start.

identical

binary tree please help
Solution

  • If you want to check if two trees are identical, you can simply simultaneously traverse the two trees. When traversing the two trees, if a node exists on one tree but not on the other, then the trees are not identical.

    You can take the recursive approach described here: https://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/

    sameTree(tree1, tree2)
1. If both trees are empty then return 1.
2. Else If both trees are non -empty
     (a) Check data of the root nodes (tree1->data ==  tree2->data)
     (b) Check left subtrees recursively  i.e., call sameTree( 
          tree1->left_subtree, tree2->left_subtree)
     (c) Check right subtrees recursively  i.e., call sameTree( 
          tree1->right_subtree, tree2->right_subtree)
     (d) If a,b and c are true then return 1.
3  Else return 0 (one is empty and other is not)

    Now if you want to check if two trees are isomorphic, there are a range of ways you could do that. For high accuracy and good performance you would probably be looking for some way to hash both the trees.