public static boolean containsTokenOfType(ASTNode root, PTFUtils.Predicate<ASTNode> predicate) {
    Queue<ASTNode> queue = new ArrayDeque<ASTNode>();

    // BFS
    queue.add(root);
    while (!queue.isEmpty())  {
      ASTNode current = queue.remove();
      // If the predicate matches, then return true.
      // Otherwise visit the next set of nodes that haven't been seen.
      if (predicate.apply(current)) {
        return true;
      } else {
        // Guard because ASTNode.getChildren.iterator returns null if no children available (bug).
        if (current.getChildCount() > 0) {
          for (Node child : current.getChildren()) {
            queue.add((ASTNode) child);
          }
        }
      }
    }

    return false;
  }
Performs a descent of the leftmost branch of a tree, stopping when either a
node with a non-null token is found or the leaf level is encountered.

@param tree
         candidate node from which to start searching

@return node at which descent stopped
ql/src/java/org/apache/hadoop/hive/ql/parse/ParseUtils.java