Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Check Subtree

problem

T1 and T2 are two very large binary trees, with T1 much bigger than T2. Create an algorithm to determine if T2 is a subtree of T1. A tree T2 is a subtree of T1 if thre exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

how to solve

I prepare two function. One is the function to determine if the 2 tree is same or not, and the other one is the function determine if the t1 is the subtree of t2. First function is implemented to check if all element is same or not recursively.

code

Remove all ads