 Data Structures -- Binary Tree -- Structurally Same, Find if 2 binary tress are structurally same?? |
|
|
|
|
  |
 Oct 27 2007, 11:33 AM
Post
#1
|
|
|
Super Member  Group: [HOSTED] Posts: 284 Joined: 1-October 07 From: India Member No.: 50,968  |
Given two binary trees, find out whether a tree is structurally same to the other.
Structurally same means that the two trees look alike or a tree looks alike a subtree of the other tree. Look for time and space complexity. Some more for readers What is a binary tree? QUOTE A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree. 
binarytree.gif ( 3.78k )
Number of downloads: 1A "binary search tree" (BST) or "ordered binary tree" is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (>). The tree shown above is a binary search tree -- the "root" node is a 5, and its left subtree nodes (1, 3, 4) are <= 5, and its right subtree nodes (6, 9) are > 5. Recursively, each of the subtrees must also obey the binary search tree constraint: in the (1, 3, 4) subtree, the 3 is the root, the 1 <= 3 and 4 > 3. Watch out for the exact wording in the problems -- a "binary search tree" is different from a "binary tree". The nodes at the bottom edge of the tree have empty subtrees and are called "leaf" nodes (1, 4, 6) while the others are "internal" nodes (3, 5, 9). For more about binary trees... Please follow the below links: http://en.wikipedia.org/wiki/Binary_tree http://cslibrary.stanford.edu/110/BinaryTrees.html http://www.nist.gov/dads/HTML/binarytree.html |
 |
 
|
|
Oct 27 2007, 01:59 PM
Post
#2
|
|
|
Newbie [Level 1] Group: Members Posts: 12 Joined: 24-October 07 Member No.: 51,949 |
Two solutions spring to mind. Firstly, you could pass the root nodes of both trees into a recursive function and compare their children. If they have an identical number & position of children, continue to recurse, otherwise unravel and report "different". If the function returns with no report of difference you have identical trees.
Alternatively, if you don't have both trees at the same time to compare, you could create a model of a tree using bit strings to denote the presense or absence of nodes. E.g. a fully populated three-level tree would be represented as 1111111 ... leave off the bottom leftmost child and you get 1110111. Then run your final bit string through a hash (e.g. md5sum) and you have a fingerprint of your tree structure. This way you'd be able to store the structure of a tree in a few bytes for future use. |
|
|
|
|
Oct 29 2007, 02:46 PM
Post
#3
|
|
|
Super Member Group: [HOSTED] Posts: 284 Joined: 1-October 07 From: India Member No.: 50,968 |
Hi Pointybirds...
Your solution works for trees that are exactly the same. But structurally same also means that the sub-tree can also be the same... So we have to do some changes in your algorithm...may be instead of passing the root to both the trees...the node which has the probability of becoming a structurally sam ecan be passed. Here is one solution suggested by one of my friends. CODE bool checksimilarity(node *p1, node *p2){ if (checkequal (p1, p2)) return true; if (checksimilarity(p1->left, p2)) return true; if (checksimilarity(p1->right, p2)) return true; return false; } CODE bool checkequal(node *p1, node *p2){ //checks whether the two nodes are pointing to null if (p1 == null && p2 == null) return true; //checks whether the two nodes in the trees are not pointing to another node. //If they are not pointing, then the similarity of the tree goes wrong. so, return false. if ((p1 == null && p2 != null) || (p1 != null && p2 == null) return false; //The trees are similar till this node, so check for their left and right subtrees. return (checkequal(p1->left, p2->left) && checkequal(p1->right, p2->right)); } No additional space required. Time complexity O(nlogn). This piece of code works good in all case... do post your comments. |
|
|
|
|
Oct 29 2007, 05:08 PM
Post
#4
|
|
|
Privileged Member Group: [HOSTED] Posts: 937 Joined: 14-April 05 From: West Chester, PA Member No.: 5,636 |
The first option that comes to my mind is send the root node into the one tree. Search the tree for this node. If that node is found, check the children to see if they are the same. If they are not, you can end. Otherwise continue to traverse. This will determine if the trees are the same or one is a subset of the other. Overall, it is time O(n) since there is no guarentee the binary tree is balanced.
|
|
|
|
|
Nov 23 2007, 12:44 PM
Post
#5
|
|
|
Newbie Group: Members Posts: 8 Joined: 22-November 07 From: Antibes, France Member No.: 53,494 |
QUOTE(fffanatics @ Oct 29 2007, 06:08 PM)  The first option that comes to my mind is send the root node into the one tree. Search the tree for this node. If that node is found, check the children to see if they are the same. If they are not, you can end. Otherwise continue to traverse. This will determine if the trees are the same or one is a subset of the other. Overall, it is time O(n) since there is no guarentee the binary tree is balanced. I am not sure it will work : it is based on the assumption that you can 'find' a node from one tree in another tree based on this node's value alone. This would actually be the case if we were looking for an algorithm which checks that two binary tree are equal or that one is equal to a subtree of the other. However, the problem here is to find whether the two trees are structurally equal[i], meaning that two nodes should be compared only by checking that they have the same children structure (none, only left, only right, or both) [i]regardless of the value. For me, I cannot think of a quicker solution than Varalu 
|
|
|
|
|
Similar Topics
|
Lo-Fi Version | Time is now: 25th July 2008 - 09:37 AM |