Given two binary trees, A and ... | CareerCup
Given two binary trees, A and B,
we can define A as a subset of B if the root of A exists in B and if we can superimpose A on B at that location without changing B. (That is, the subtrees from the root of A and the node in B that is the same as the root of A are the same),
Example:
A:
5
4 7
B:
6
5 12
4 7 8 10
A is a subset of B in this case.
B1:
6
5 12
4 7 8 10
1
A is still a subset of B1, even though B1 extends one more level than A.
Write an algorithm to determine if one tree is a subset of another tree.
Generally, recursion is the more "intuitive" method to used to solve tree type problems. However, I personally believe that, if you can point out that recursion is cache unfriendly and sometimes wasteful of program stack, then you have an edge against other interviewees who did not point out this. Therefore, I think it is best that we DO NOT use recursion to solve this problem. Therefore, some key data structures to use would be the stack (for depth-first) and the queue (for breath-first).
Read full article from Given two binary trees, A and ... | CareerCup
Given two binary trees, A and B,
we can define A as a subset of B if the root of A exists in B and if we can superimpose A on B at that location without changing B. (That is, the subtrees from the root of A and the node in B that is the same as the root of A are the same),
Example:
A:
5
4 7
B:
6
5 12
4 7 8 10
A is a subset of B in this case.
B1:
6
5 12
4 7 8 10
1
A is still a subset of B1, even though B1 extends one more level than A.
Write an algorithm to determine if one tree is a subset of another tree.
Generally, recursion is the more "intuitive" method to used to solve tree type problems. However, I personally believe that, if you can point out that recursion is cache unfriendly and sometimes wasteful of program stack, then you have an edge against other interviewees who did not point out this. Therefore, I think it is best that we DO NOT use recursion to solve this problem. Therefore, some key data structures to use would be the stack (for depth-first) and the queue (for breath-first).
Read full article from Given two binary trees, A and ... | CareerCup
