java - Does a binary tree contain another tree? -

alright guys, asked question in interview today , goes this:

"tell if 1 binary tree contained inside binary tree or not (contains implies both in structure , value of nodes)"

i thought of following approach:

flatten larger tree as:

{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}} 

(i did write code this, {-} implies empty left or right sub-tree, each sub-tree enclosed within {} paranthesis)

now smaller sub-tree need match pattern:

{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}} 

where {.*} denotes empty or non-empty sub-tree.

at time thought, trivial regex pattern matching problem in java bamboozled. feel, have transformed problem (created 1 monster out of another).

is there simple regex 1 liner match these patterns? understand there might other approaches solve problem , might not best one. wonder if solvable.

i'm not sure interviewer meant "contained inside binary tree". if interviewer asking method check whether subtree of b, here 1 method not require regex @ all:

• flatten trees , b using preorder traversal strings, say, prea , preb
• flatten trees , b using inorder traversal strings, say, ina , inb
• make sure include null leaves in strings (using whitespaces example)
• check if prea substring of preb , ina substring of inb

the reason wanna include null leaves because when multiple nodes have same value, preorder , inorder may not enough. here example:

                         b     b       c  c         d       b d           c       d  

you can check out:

checking subtrees using preorder , inorder strings

also read more info on preorder , inorder traversals of binary trees:

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

now, if didn't mean subtrees, problem may become more complicated depending on interviewer meant "part". @ question subgraph isomorphism problem (trees subset of graphs) , np-complete.

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

there may better approaches since trees more restricted , simpler graphs.