Re: [algogeeks] Re: Check if one tree is sub tree of other
thank you for telling the unworkability of my algo.
i did not see the puzzle completely. my algo works only for BST.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 8:49 PM, Lucifer sourabhd2...@gmail.com wrote:
@All
[ Let the tree to be searched in be 'T' and the subtree to be matched
be 'S']
If i understood the previous posts correctly.. then basically we
discussed about 2 methods:
1) Brute force, wherein we consider each node of the 'T' as the root
of new subtree and try to compare it with 'S'.
Complexity - O( |T| * |S| ) ... ( |X| = size of 'X' )
2) Preorder with special characters...
Time complexity:-
Time taken to generate the preordered string for
'T' :- 2* |T| + 1
Time taken to generate the preordered string for
'S' :- 2* |S| + 1
Time taken to find a match : O(2* |T|) + O(2* |S|)
Hence, total time complexity : O(|T|) .. [assuming that |T| =|
S| ]
Space complexity: 2*( |T| + |S| + 1)
I think we can come up with a third method where the time complexity
will be of the order of O(|T|) with constant space..
Here is the idea,
As we know that the subtree in the question is a perfect subtree, we
can use it to develop a O(|T|) algo..
If we know the count of nodes for each perfect subtree of |T| then for
all those subtrees having the count equal to |S| we will perform a
check to see if the subtrees match, otherwise we won't..
Basic operations:
1) Count the no. of nodes of |S| : CountNodes(node * root) ( Time
Complexity : |S|)
2) Check whether 2 trees are equal : isTREqual(node *T1, node *T2)
( Time Complexity : |S|, as we are going to check only for those
subtrees of |T| whose count is equal to |S|)
3) Modify the CountNodes(node *root) API to calculate the count of the
subtrees as well as check with the subtree of 'T' is equal to 'S' when
the counts match.
Regarding time complexity of the above algo:
As we already know the time complexity of operations 1 and 2, lets
talk about operation 3.
The count procedure will take |T| time in total...
What about the match procedure ?
Say that we have identified subtrees T1, T2...Tn.. whose count is
equal to |S|, hence the time taken by the tree match procedure will be
|S| * (n)..
Lets look at this derivation in a slightly different way exploiting
one of the properties of the found subtrees:
Now, as we know that all the subtrees of T having the same node count |
S| can't share nodes among them...
hence,
|T1| + |T2| + ... |Tn| = |T| , i.,e |S| * (n) = |T| , equality holds
when S = T..
Hence Time complexity (for operation 3) is equal to 2*|T|..
Total complexity: time taken by operation (1) + (3)
: |S| + 2*|T| = O(|T|)
---
Pseudocode:
// I m not jolting down the code for CountNodes and isTREqual..
// Also, currently assuming that |S| and |T| are not null trees.. well
this special case can be handled, if required.. but i don't think its
a valid use case..
bool areTreesSame(node *T, node *S, int countS, int *nCount)
{
int leftCount=0, rightCount=0;
if (T == NULL)
return false;
if ( areTreesSame(T- left, S, countS, leftCount) ||
areTreesSame(T- right, S, countS, rightCount)
)
return true;
else
{
*nCount = leftCount+rightCount+1;
if(nCountS == *nCount)
return isTREqual(T, S);
else
return false;
}
}
---
On Mar 21, 5:04 pm, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
Yeah..i wrote sumthig similar..i placed L for left null and R for
right null..and then checked for substring in preorder traversal..i
dont know if its correct or not..
On 3/21/12, atul anand atul.87fri...@gmail.com wrote:
@amrit : i guess this will work.
On Wed, Mar 21, 2012 at 1:51 PM, amrit harry dabbcomput...@gmail.com
wrote:
i have an idea to solve this.
use preorder traversal and a sentinal(#) on the place of Null nodes.
lets take a example
Main tree 1
subtree 1
2 3
2
4
3
preorder travesal for Main: 12##34###for sub tree 12#3###
now chk for the sub string in Main string
one more case
Main1
/ \
34
/ \
51
/ \
34
preorder traversal= 1353##4##1##4##
sub
5
/\
3 4
preorder traversal 53##4##
now this substring exist in Main substring so it is a sub tree
correct me if me wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 1:34 PM,
[algogeeks] Re: Check if one tree is sub tree of other
I'll point out that if you are building a system where this problem actually occurs (as in generating DAGs in a compiler expression optimizer), you can nearly always engineer the problem down to O(log(| T|)) if T is balanced and O(|T|) in the worst case. Trees need parent pointers, and also a map must be maintained HashMapTripleNode, Node, Data, Node nodeMap; where the key holds the children and data value of the corresponding node that has already been generated. The system never constructs a new node without first checking this global map to see if a node with the right pair of children and data has already been generated. If so, the existing node is used. Otherwise a new one is created and added to the map. Now within this system, checking tree equality is the same as checking root pointer equality. (Proof is by induction over the height of trees!) So two trees can be compared in one machine instruction. For the subtree test, just follow parent pointers from S to its root checking each node to see if it's the root of T. On Mar 20, 8:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: How to check if one binary tree is a sub tree of other? Any Solution other then bruteforce? Prototype bool check(node *t1,node *subtree) -- Sent from my mobile device *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Check if one tree is sub tree of other
@sidarth
your method would not work it think.
let a case
sub tree: 4Main tree:
6
5 6
4 7
5
8
inorder traversal of sub tree str1= 5,4,6 and inorder traversal of Main
tree str2=5,4,6,7,8
and str1 is subset of str2 but the sub-tree is not actually a sub tree...
correct me if im wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 11:20 AM, Dheeraj Sharma
dheerajsharma1...@gmail.com wrote:
No..am nt talking about binary search tree..bt about binary tree.. It
was asked in my amazon written
@shady..doing the substring search..as we have to search for subset of
tree..it searchng substrn might find some false nodes..that doesnt
belong to that subtree
On 3/21/12, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
AMRIT
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Check if one tree is sub tree of other
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.comwrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Check if one tree is sub tree of other
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.com
wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Check if one tree is sub tree of other
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady sinv...@gmail.com wrote:
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.com wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
AMRIT
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
Re: [algogeeks] Re: Check if one tree is sub tree of other
i have an idea to solve this.
use preorder traversal and a sentinal(#) on the place of Null nodes.
lets take a example
Main tree 1
subtree 1
2 3
2
4
3
preorder travesal for Main: 12##34###for sub tree 12#3###
now chk for the sub string in Main string
one more case
Main1
/ \
34
/ \
51
/ \
34
preorder traversal= 1353##4##1##4##
sub
5
/\
3 4
preorder traversal 53##4##
now this substring exist in Main substring so it is a sub tree
correct me if me wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 1:34 PM, amrit harry dabbcomput...@gmail.comwrote:
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady sinv...@gmail.com wrote:
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.com wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and
one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Re: [algogeeks] Re: Check if one tree is sub tree of other
@amrit : i guess this will work.
On Wed, Mar 21, 2012 at 1:51 PM, amrit harry dabbcomput...@gmail.comwrote:
i have an idea to solve this.
use preorder traversal and a sentinal(#) on the place of Null nodes.
lets take a example
Main tree 1
subtree 1
2 3
2
4
3
preorder travesal for Main: 12##34###for sub tree 12#3###
now chk for the sub string in Main string
one more case
Main1
/ \
34
/ \
51
/ \
34
preorder traversal= 1353##4##1##4##
sub
5
/\
3 4
preorder traversal 53##4##
now this substring exist in Main substring so it is a sub tree
correct me if me wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 1:34 PM, amrit harry dabbcomput...@gmail.comwrote:
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady sinv...@gmail.com wrote:
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.com wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left,
t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all
the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and
one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this
[algogeeks] Re: Check if one tree is sub tree of other
Yeah..i wrote sumthig similar..i placed L for left null and R for
right null..and then checked for substring in preorder traversal..i
dont know if its correct or not..
On 3/21/12, atul anand atul.87fri...@gmail.com wrote:
@amrit : i guess this will work.
On Wed, Mar 21, 2012 at 1:51 PM, amrit harry dabbcomput...@gmail.comwrote:
i have an idea to solve this.
use preorder traversal and a sentinal(#) on the place of Null nodes.
lets take a example
Main tree 1
subtree 1
2 3
2
4
3
preorder travesal for Main: 12##34###for sub tree 12#3###
now chk for the sub string in Main string
one more case
Main1
/ \
34
/ \
51
/ \
34
preorder traversal= 1353##4##1##4##
sub
5
/\
3 4
preorder traversal 53##4##
now this substring exist in Main substring so it is a sub tree
correct me if me wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 1:34 PM, amrit harry
dabbcomput...@gmail.comwrote:
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady sinv...@gmail.com wrote:
seems correct with pre-order traversal if not give some example
On Wed, Mar 21, 2012 at 10:32 AM, Mahesh Thakur
tmahesh...@gmail.comwrote:
First Tree:
1
2 3
4 5 67
Inorder traverse will be : 4251637
Second Tree:
6
1 3
Inorder traversal is 163.
But they second tree is not subset. let me know if i got the question
wrong.
On Wed, Mar 21, 2012 at 10:27 AM, shady sinv...@gmail.com wrote:
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.com wrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.com wrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left,
t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all
the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and
one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching
sub
tree.
If they are binary search trees, it could be more efficient. Did
you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to
[algogeeks] Re: Check if one tree is sub tree of other
@All
[ Let the tree to be searched in be 'T' and the subtree to be matched
be 'S']
If i understood the previous posts correctly.. then basically we
discussed about 2 methods:
1) Brute force, wherein we consider each node of the 'T' as the root
of new subtree and try to compare it with 'S'.
Complexity - O( |T| * |S| ) ... ( |X| = size of 'X' )
2) Preorder with special characters...
Time complexity:-
Time taken to generate the preordered string for
'T' :- 2* |T| + 1
Time taken to generate the preordered string for
'S' :- 2* |S| + 1
Time taken to find a match : O(2* |T|) + O(2* |S|)
Hence, total time complexity : O(|T|) .. [assuming that |T| =|
S| ]
Space complexity: 2*( |T| + |S| + 1)
I think we can come up with a third method where the time complexity
will be of the order of O(|T|) with constant space..
Here is the idea,
As we know that the subtree in the question is a perfect subtree, we
can use it to develop a O(|T|) algo..
If we know the count of nodes for each perfect subtree of |T| then for
all those subtrees having the count equal to |S| we will perform a
check to see if the subtrees match, otherwise we won't..
Basic operations:
1) Count the no. of nodes of |S| : CountNodes(node * root) ( Time
Complexity : |S|)
2) Check whether 2 trees are equal : isTREqual(node *T1, node *T2)
( Time Complexity : |S|, as we are going to check only for those
subtrees of |T| whose count is equal to |S|)
3) Modify the CountNodes(node *root) API to calculate the count of the
subtrees as well as check with the subtree of 'T' is equal to 'S' when
the counts match.
Regarding time complexity of the above algo:
As we already know the time complexity of operations 1 and 2, lets
talk about operation 3.
The count procedure will take |T| time in total...
What about the match procedure ?
Say that we have identified subtrees T1, T2...Tn.. whose count is
equal to |S|, hence the time taken by the tree match procedure will be
|S| * (n)..
Lets look at this derivation in a slightly different way exploiting
one of the properties of the found subtrees:
Now, as we know that all the subtrees of T having the same node count |
S| can't share nodes among them...
hence,
|T1| + |T2| + ... |Tn| = |T| , i.,e |S| * (n) = |T| , equality holds
when S = T..
Hence Time complexity (for operation 3) is equal to 2*|T|..
Total complexity: time taken by operation (1) + (3)
: |S| + 2*|T| = O(|T|)
---
Pseudocode:
// I m not jolting down the code for CountNodes and isTREqual..
// Also, currently assuming that |S| and |T| are not null trees.. well
this special case can be handled, if required.. but i don't think its
a valid use case..
bool areTreesSame(node *T, node *S, int countS, int *nCount)
{
int leftCount=0, rightCount=0;
if (T == NULL)
return false;
if ( areTreesSame(T- left, S, countS, leftCount) ||
areTreesSame(T- right, S, countS, rightCount)
)
return true;
else
{
*nCount = leftCount+rightCount+1;
if(nCountS == *nCount)
return isTREqual(T, S);
else
return false;
}
}
---
On Mar 21, 5:04 pm, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
Yeah..i wrote sumthig similar..i placed L for left null and R for
right null..and then checked for substring in preorder traversal..i
dont know if its correct or not..
On 3/21/12, atul anand atul.87fri...@gmail.com wrote:
@amrit : i guess this will work.
On Wed, Mar 21, 2012 at 1:51 PM, amrit harry dabbcomput...@gmail.comwrote:
i have an idea to solve this.
use preorder traversal and a sentinal(#) on the place of Null nodes.
lets take a example
Main tree 1
subtree 1
2 3
2
4
3
preorder travesal for Main: 12##34### for sub tree 12#3###
now chk for the sub string in Main string
one more case
Main 1
/ \
3 4
/ \
5 1
/ \
3 4
preorder traversal= 1353##4##1##4##
sub
5
/ \
3 4
preorder traversal 53##4##
now this substring exist in Main substring so it is a sub tree
correct me if me wrong.
Thanks
Amrit
On Wed, Mar 21, 2012 at 1:34 PM, amrit harry
dabbcomput...@gmail.comwrote:
@shady consider this case
Main tree 1
subtree 1
2 3
2
4
3
preorder of Main= 1234 subtree= 123 but not subtree
On Wed, Mar 21, 2012 at 1:24 PM, shady
[algogeeks] Re: Check if one tree is sub tree of other
Geeksforgeeks gives brute force approach @shady.. No its not..the sub tree should be a perfect sub tree..there should be no node below that sub tree in the main tree On 3/20/12, rahul sharma rahul23111...@gmail.com wrote: http://www.geeksforgeeks.org/archives/13942 then call for On Tue, Mar 20, 2012 at 7:16 PM, shady sinv...@gmail.com wrote: 5 /\ 3 4 is this subtree of 1 / \ 34 / \ 51 / \ 34 / 9 ? On Tue, Mar 20, 2012 at 5:54 PM, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: How to check if one binary tree is a sub tree of other? Any Solution other then bruteforce? Prototype bool check(node *t1,node *subtree) -- Sent from my mobile device *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sent from my mobile device *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Check if one tree is sub tree of other
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Check if one tree is sub tree of other
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Check if one tree is sub tree of other
get the inorder traversal both tree (into strings) check weather one string
substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Check if one tree is sub tree of other
@Sid +100
On Wed, Mar 21, 2012 at 10:20 AM, siddharam suresh
siddharam@gmail.comwrote:
get the inorder traversal both tree (into strings) check weather one
string substring of other if yes then one tree is sub tree of other.
Thank you,
Sid.
phone:+91-8971070727,
+91-9916809982
On Wed, Mar 21, 2012 at 9:23 AM, HARSHIT PAHUJA
hpahuja.mn...@gmail.comwrote:
bool isSubtree(Tree * A,Tree *B)
{
if(!B) return true;
if(!A)return false;
if(A-data==B-data)
return (isSubtree(A-left,B-left)
isSubtree(A-right,B-right));
else
return (isSubtree(A-left,B) isSubtree(A-right,B));
}
}
On Wed, Mar 21, 2012 at 2:33 AM, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
HARSHIT PAHUJA
M.N.N.I.T.
ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Check if one tree is sub tree of other
No..am nt talking about binary search tree..bt about binary tree.. It
was asked in my amazon written
@shady..doing the substring search..as we have to search for subset of
tree..it searchng substrn might find some false nodes..that doesnt
belong to that subtree
On 3/21/12, Don dondod...@gmail.com wrote:
bool equals(node *t1, node *t2)
{
return (t1 t2) ? (t1-value == t2-value) equals(t1-left, t2-
left) equals(t1-right, t2-right) : !t1 !t2;
}
bool check(node *t1, node *subtree)
{
return t1 ? equals(t1, subtree) || check(t1-left, subtree) ||
check(t1-right, subtree) : !subtree;
}
On average this is the same as a traversal, but worst case could be
very slow. Imagine a large tree with millions of nodes, where all the
nodes = 1, and a somewhat smaller subtree with 100,000 nodes=1 and one
node at the far right of the tree = 2. It would require a lengthy
comparision at each node which would ultimately find no matching sub
tree.
If they are binary search trees, it could be more efficient. Did you
mean to ask about binary search trees?
Don
On Mar 20, 7:24 am, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
How to check if one binary tree is a sub tree of other?
Any Solution other then bruteforce?
Prototype
bool check(node *t1,node *subtree)
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sent from my mobile device
*Dheeraj Sharma*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
