Learn basic concept of c , c++ and python programming in regularcodes.com

Spread the post

Check if two trees are identical

Write an efficient algorithm to check given two tree are Identical. In this post given a iterative solution using of stack.

Following conditions of identical tree.

1) number of nodes are equal in both given tree.

2) visit both tree every node similar manner(inorder , peroder, post order choose any one). there parent node values are same. if not equal that means there are not identical of tree.

Example

Function to check identical of two binary tree.

Structure of given tree.

Stack Areamainresult (int) ? root1(pointer)root2(pointer)top(pointer) NULLinorder_showtemp(pointer) Heap Areastruct Treedata (int)= 90left (pointer) right (pointer) struct Treedata (int)= 10left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 80left (pointer) right (pointer) struct Treedata (int)= 77left (pointer)= NULLright (pointer) struct Treedata (int)= 60left (pointer)= NULLright (pointer) struct Treedata (int)= 30left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 50left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 90left (pointer) right (pointer) struct Treedata (int)= 10left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 80left (pointer) right (pointer) struct Treedata (int)= 77left (pointer)= NULLright (pointer) struct Treedata (int)= 60left (pointer)= NULLright (pointer) struct Treedata (int)= 30left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 50left (pointer)= NULLright (pointer)= NULL

Program for check two given tree are identical. Time complexity O(n).


Output

Stack Areamainresult (int) ? root1(pointer)root2(pointer)top(pointer) NULLcheck_identicalroot1(pointer)root2(pointer)status (int) =1top(pointer)pushnew_node(pointer)node1(pointer)node2(pointer)top(pointer) Heap Areastruct Treedata (int)= 90left (pointer) right (pointer) struct Treedata (int)= 10left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 80left (pointer) right (pointer) struct Treedata (int)= 77left (pointer)= NULLright (pointer) struct Treedata (int)= 60left (pointer)= NULLright (pointer) struct Treedata (int)= 30left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 50left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 90left (pointer) right (pointer) struct Treedata (int)= 10left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 80left (pointer) right (pointer) struct Treedata (int)= 77left (pointer)= NULLright (pointer) struct Treedata (int)= 60left (pointer)= NULLright (pointer) struct Treedata (int)= 30left (pointer)= NULLright (pointer)= NULLstruct Treedata (int)= 50left (pointer)= NULLright (pointer)= NULLstruct Stackroot1 (pointer) root2 (pointer) next (pointer)= ?

Execution Process Try it Yourself

Spread the post

Recommended Posts: