I was able to get attributes about an user by doing queries on LDAP using Python ldap but I don't know how to obtain his DN.
Remark: Doing CN=sAMAccount,base_dn) is not valid because the user can be somewhere in another sub-tree.
Which is the proper way of getting the DN for an user for which I do have the sAMAccount?
The search result contains:

A list of search result entries. Each search result entry in the list contains the distinguished name of the entry and a (partial) attribute list

or

A list of search result references. Each search result reference contains a sequence of URIs

After the entries or references comes a single search result done message.
Therefore, if any entries matched, they are returned in the list of search result entries, each of which contains the distinguished name of the entry that was matched. Your python API documentation should contain information as to how to extract the distinguished name of the entry that matched.
How do I get the full DN, distinguishedName of an user with python ldap?