varalu
Oct 27 2007, 11:33 AM
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 readersWhat 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.
[attachment=859:binarytree.gif]A "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_treehttp://cslibrary.stanford.edu/110/BinaryTrees.htmlhttp://www.nist.gov/dads/HTML/binarytree.html
Reply
pointybirds
Oct 27 2007, 01:59 PM
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.
Reply
varalu
Oct 29 2007, 02:46 PM
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.
Reply
fffanatics
Oct 29 2007, 05: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.
Reply
apicolet
Nov 23 2007, 12:44 PM
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 
Reply
Similar Topics
Keywords : data structures binary structurally binary tress structurally- Data Structures -- Linked List -- Reverse
- Reverse a linked list (3)
Give an algorithm to reverse a linked list with a time complexity of O(n) and minimal space
complexity. What is a linked list? Search trap17.com. i Have already answered this question in
one of my older questions. Solution 1 Here is one simple solution... CODE Void
ReverseList(node* head) { node *temp,*current,*result; temp=null; result=null;
current=head; while(current!=null) { temp=current->next;
current->next=result; result=current; current=temp; }
head=result; ...
Data Structure -- Permutations
- (1)
Data Structures -- String -- Palindrome
- Check if a string is a palindrome... (4)
Write an algorithm to check whether a given string is palindrome or not in time complexity O(n)
What is a palindrome?? QUOTE A palindrome is a word, phrase, number or other sequence of units
that has the property of reading the same in either direction (the adjustment of punctuation and
spaces between words is generally permitted). Composing literature in palindromes is an example of
constrained writing. The word "palindrome" was coined from Greek roots palin
(πάλιν; "back") and dromos (δρóμος; "way,
direction") by...
Data Structures -- Linked List -- Point Of Merging
- (2)
Given two singly linked lists with both of them merging at some point. Find the position at which
they merge. Eg: 1->30->50->65->2->59 88->46->65->2->59
The above two linked lists merge at 65. Find this node where they merge.. Question
Courtesy: Antony(Friend) One possible Answer A simple answer would be to find the length of
both the linked lists and have two pointers, one for each linked list. Move (difference in lengths)
steps in the longer linked lists and then start moving both the pointers by one every t...
Data Structures -- Linked List
- Find the nth last element in linked list. (7)
Given a linked list, find the 5th last element with Time complexity O(n) and minimal space
complexity. Note: If you know the answer and if you feel it is simple also please post the
answers so that others will come to know about the answers. What is a linked list?? /* this is for
your further reference and reading */ QUOTE In computer science, a linked list is one of the
fundamental data structures, and can be used to implement other data structures. It consists of a
sequence of nodes, each containing arbitrary data fields and one or two references ("links") po...
Data Structure -- Queue -- Implement Using Stack
- (0)
Implement a Queue using a stack. No restriction on space complexity. One possible Solutions a
costly procedure... 1. Use a temp stack 2. Insertion into queue - Push the element into the
original stack 3. Deletion from queue - Pop all the elements from stack into a temp stack
- pop out the first element from the temp stack - pop all the remaining elements back to the
original stack What is a queue? QUOTE A queue is a particular kind of collection in which
the entities in the collection are kept in order and the principal (or only) operation...
Data Structure -- Trees -- Threaded Binary Tree
- (0)
A binary tree having a loop is known as a threaded binary tree. Have a look at the attachment to
have an idea of a threaded binary tree.... A's right child is B and B's left child is A.
Write an algorithm to find out whether the given tree is a threaded binary tree. Look for time
and space complexity....
Data Structures -- String -- Arrange Based On Repetition
- String data structure (1)
Consider a string with any number of elements occurring any number of time. Rearrange the string
in such a way that the alphabet with most occurrence occurs in the followed by the next most
occurring alphabet and so on... It should also be seen that the alphabets should occur frequency
number of times. Example: Input : abcdaeghzabcdbhb Output : bbbbaaaccddhhegz ...
Data Structures -- Expression Trees
- (0)
Construct an expression tree for the expression (a || /cool.gif" style="vertical-align:middle"
emoid="B)" border="0" alt="cool.gif" /> && (c || d) After constructing the tree convert the tree to
correspond to the associative property of the given expression. Eg: (1 + 2) * ( 3 + 4) = (1 * 3) +
(1 * 4) + (2 * 3) + (2 * 4) Similar to that, from the constructed expression tree, construct a new
expression tree such that inorder traversal of the new tree will be associative value of the given
expression Inorder traversal of the new tree should be (a && c) || (a && d) || (...
Data Structure -- Arrays -- Odd Number Of Elements
- (0)
Given an array of elements with many numbers occurring even number of times and two numbers
occurring odd number of times. Find out the two numbers that occur odd number of times. example:
Elements in array -- 14433446 The expected result is 1 and 6 One solution 1. Find max of the
array 2. Hash Function : element/max value 3. Repeat to all elements... 4. Find frequency... yo will
get the 2 elements with odd frequency. but this is not the optimal.... Do find more solutions to
this and post it. Look for time and space complexity. Another Solution one more s...
Data Structures -- Binary Tree -- Mirror Image
- Binary Tree -- Mirror Image (0)
Given a binary tree, write an algorithm to find its mirror image with minimal time and space
complexities. Note: If you know the answer and if you feel it is simple also please post the
answers so that others will come to know about the answers. This question was sent by my friend
through mail. Solutions Suggested Sol 1 CODE void PrintMirror(node *root) {
if(node!=NULL) PrintMirror(root->right);
Printf(root->data); PrintMirror(root->left); } In case of
implementation using...
Data Structure Questions
- (4)
Question 1 Reply the solutions if you have any so that we can discuss... Given an array of n
elements (containing only positive numbers) and sum, X. Find the first two elements in the array
that sum upto X eg: Array of elements - {2, 3,1000, 200, 51, 88, 29, 49, 65, 40, 98, 12, 3}
Sum - 100. The answer for the above sample is 51, 49. There are other possiblities
also, but the first two numbers summing upto the given sum, 100 should be taken. How will you do
this with minimal space and time complexities? Question 2 Given two nodes of ...
Limiting Returned Data To Last X Fields With Sql
- (2)
Hello, I'm currently developing a social-networking site in ColdFusion and several aspects of
the site require me to return a limited number of records for display (e.g. displaying the last 3
news items in the left-hand column on the front page, etc.). I currently only have a small SQL
"cheet sheet" and what my ColdFusion reference book tells me, and I cannot find anything anywhere
about limiting the data returned from a SELECT statement to the last X number of records. Any help
is appreciated! Thanks, zeeman48...
A Question About Data Collecting Program
- usually found in registers (1)
does anyone know which programming language is used to make applications like those used in shops
and malls where the sales assistant will enter name of a product and all its details will come up
and whn someone makes a purchase the details will go to a database , i need to know which language
is used and also which platform is used ,thanks in advance /laugh.gif"
style="vertical-align:middle" emoid=":lol:" border="0" alt="laugh.gif" /> Please read the rules.
The What Is..? forum is for answering a common question or telling everybody about what
interesting fact you ...
Looking for data, structures, binary, tree, structurally, 2, binary, tress, structurally,
|
|
Searching Video's for data, structures, binary, tree, structurally, 2, binary, tress, structurally,
|
advertisement
|
|
