Sensitive knowledge hiding is the problem of removing sensitive knowledge from databases before publishing. The problem is extensively studied in the context of relational databases to hide frequent itemsets and association rules. Recently, sequential pattern hiding from sequential (both sequence and spatio-temporal) databases has been investigated [1]. With the ever increasing versatile application demands, new forms of knowledge and databases should be addressed as well. In this work, we address the knowledge hiding problem in the context of tree and graph databases. For these databases efficient frequent pattern mining algorithms have already been developed in the literature. Since, some of the discovered patterns may be attributed as sensitive, we develop appropriate sanitization techniques to protect the privacy of the sensitive patterns. (C) 2011 Elsevier B.V. All rights reserved.