algorithm - Checking if A is a part of binary tree B -

let's have binary trees , b , want know if "part" of b. not talking subtrees. want know if b has nodes , edges does.

my thoughts since tree graph, , view question subgraph isomorphism problem (i.e. checking see if subgraph of b). according wikipedia np-complete problem.

http://en.wikipedia.org/wiki/subgraph_isomorphism_problem

i know can check if subtree of b or not o(n) algorithms (e.g. using preorder , inorder traversals flatten trees strings , checking substrings). trying modify little see if can test "parts" well, no avail. i'm stuck.

are there other ways view problem other using subgraph isomorphism? i'm thinking there must faster methods since binary trees more restricted , simpler versions of graphs.

thanks in advance!

edit: realized worst case brute force method question take o(m * n), polynomial. guess isn't np-complete problem after all. next question is, there algorithm faster o(m*n)?

i approach problem in 2 steps:

1. find root of a in b (either bfs of dfs)
2. verify a contained in b (giving starting node), using recursive algorithm, below (i concocted same crazy pseudo-language, because didn't specify language. think should understandable, no matter background). note a node a (initially root) , b node b (initially node found in step 1)

function checktrees(node a, node b) returns boolean     if not exist or b not exist         // base of recursion         return false     else if different b         // compare current nodes         return false     else         // check children of         boolean leftfound = true         boolean rightfound = true          if a.left exists             // try match left child of             // every possible neighbor of b             leftfound = checktrees(a.left, b.left)                        or checktrees(a.left, b.right)                        or checktrees(a.left, b.parent)          if a.right exists             // try match right child of             // every possible neighbor of b             leftfound = checktrees(a.right, b.left)                        or checktrees(a.right, b.right)                        or checktrees(a.right, b.parent)          return leftfound , rightfound 

about running time: let m number of nodes in a , n number of nodes in b. search in first step takes o(n) time. running time of second step depends on 1 crucial assumption made, might wrong: assumed every node of a equal at most 1 node of b. if case, running time of second step o(m) (because can never search far in wrong direction). total running time o(m + n).

while writing down assumption, start wonder whether that's not oversimplifying case...