How to hierarchical query in PostgreSQL with language-dependent data

... the expected order should be compliant with tree hierarchy and alphabetical order in English (at every depth level),

The additional difficulty is that category_lang(title, lang_code) is not defined UNIQUE, so we need to sort by title and category_id (as tiebreaker) on every level - which is hard to implement for a dynamic number of levels. An array of composite type can solve the conundrum.

Your displayed results do not currently comply with your requirement. 'Three' should sort before 'Two' according to English sorting rules. The result of the following query implements your requirement:

Create once per database:

CREATE TYPE title_id AS (title varchar(128), id int);

Then use a recursive CTE to generate an array of this composite type according to its path.

WITH RECURSIVE tree AS (
   SELECT c.id AS cat_id, c.parent_id, c.tree_depth
        , l.id AS lang_id, l.title, l.lang_code
        , ARRAY[(l.title, l.category_id)::title_id] AS sort_arr
   FROM   category      c 
   JOIN   category_lang l ON l.category_id = c.id
                         AND l.lang_code = 'EN'
   WHERE  c.parent_id IS NULL  -- root cat

   UNION ALL
   SELECT c.id AS cat_id, c.parent_id, c.tree_depth
        , l.id AS lang_id, l.title, l.lang_code
        , sort_arr || (l.title, l.category_id)::title_id
   FROM   tree          t
   JOIN   category      c ON c.parent_id = t.cat_id
   JOIN   category_lang l ON l.category_id = c.id
                         AND l.lang_code = t.lang_code
    )
SELECT cat_id, parent_id, tree_depth, lang_id, title 
FROM   tree
ORDER  BY sort_arr;

db<>fiddle here

Closely related with more explanation and details:

• Retrieving full hierarchy sorted by a column under PostgreSQL's Ltree module

COLLATE?

But that's not all. The simple solution sorts by the default collation of your database, which seems inappropriate for different languages.

Every language has its own collation rules, or typically several of them, depending on the region of the world and other political / cultural rules. The "language" is not enough to specify exact rules for sorting. The precise locale matters. Postgres implements collation-aware sorting with the COLLATE keyword. You would have to store the actual precise collation in addition to the language, and use it to sort properly.

Also, indexes depend on the exact COLLATION. You might consider multiple partial indexes with different collation. Lots of tricky stuff that goes beyond the scope of this question. See:

• How to choose a collation for international database?
• PostgreSQL 9.1 using collate in select statements

Asides

• Your trigger is not safe against race conditions between concurrent writes. For the purpose of this query we do not need a persisted tree_depth at all. We could easily generate it in the rCTE. Consider dropping the column tree_depth and the trigger.

• A FK constraint seems to be missing in table category_lang:

   , FOREIGN KEY (category_id) REFERENCES category (id)
  

• Consider text instead of varchar(n) and char(n). See:

  • Any downsides of using data type "text" for storing strings?
  • Should I add an arbitrary length limit to VARCHAR columns?

• Consider an IDENTITY column instead of serial:

  • Auto increment table column

Before Erwin answered with a much simpler solution, I made this recursive approach by myself. It works better inserting a virtual root category, which allow us to retrive the whole tree from a single entry point.

create or replace function list_category_tree (
    _category_id integer,
    _lang_code char(2)
)
returns setof category
as $$
declare
    _child_category category;
begin
    -- return the passed category
    return query
    select * from category where id = _category_id;

    -- loop over the passed category children
    for _child_category in 
        select tc.* 
        from category tc
        join category_lang tl on tl.category_id = tc.id and tl.lang_code = _lang_code
        where tc.parent_id = _category_id
        order by tl.title asc
    loop
        -- recursively look for every children childrens
        return query 
        select * from list_category_tree(_child_category.id, _lang_code);
    end loop;
end;
$$ language plpgsql;

A simple test could be

select * 
from list_category_tree (0, 'EN') as tc
join category_lang tl on tl.category_id = tc.id and tl.lang_code = 'EN';

id |parent_id|tree_depth|id|category_id|lang_code|title        |
---|---------|----------|--|-----------|---------|-------------|
  1|         |         0| 1|          1|EN       |One          |
 11|        1|         1| 4|         11|EN       |One.One      |
 13|        1|         1| 6|         13|EN       |One.Three    |
 12|        1|         1| 5|         12|EN       |One.Two      |
  2|         |         0| 2|          2|EN       |Two          |
 21|        2|         1| 7|         21|EN       |Two.One      |
211|       21|         2|10|        211|EN       |Two.One.One  |
213|       21|         2|12|        213|EN       |Two.One.Three|
212|       21|         2|11|        212|EN       |Two.One.Two  |
 22|        2|         1| 8|         22|EN       |Two.Two      |
  3|         |         0| 3|          3|EN       |Three        |
 31|        3|         1| 9|         31|EN       |Three.One    |


select * 
from list_category_tree (0, 'ES') as tc
join of_category_lang tl on tl.category_id = tc.id and tl.lang_code = 'ES';

id |parent_id|tree_depth|id|category_id|lang_code|title       |
---|---------|----------|--|-----------|---------|------------|
  2|        0|         1|14|          2|ES       |Dos         |
 22|        2|         2|20|         22|ES       |Dos.Dos     |
 21|        2|         2|19|         21|ES       |Dos.Uno     |
212|       21|         3|23|        212|ES       |Dos.Uno.Dos |
213|       21|         3|24|        213|ES       |Dos.Uno.Tres|
211|       21|         3|22|        211|ES       |Dos.Uno.Uno |
  3|        0|         1|15|          3|ES       |Tres        |
 31|        3|         2|21|         31|ES       |Tres.Uno    |
  1|        0|         1|13|          1|ES       |Uno         |
 12|        1|         2|17|         12|ES       |Uno.Dos     |
 13|        1|         2|18|         13|ES       |Uno.Tres    |
 11|        1|         2|16|         11|ES       |Uno.Uno     |

having inserted the root node as

insert into of_category (parent_id, id) values 
(null, 0),

(null, 1),
(null, 2),
(null, 3),

(1, 11),
(1, 12),
(1, 13),

(2, 21),
(2, 22),
(3, 31),

(21, 211),
(21, 212),
(21, 213);

-- lang_code = 'EN'
insert into of_category_lang (category_id, title, lang_code) values 
(0, 'Root', 'EN'),

(1, 'One',   'EN'),
(2, 'Two',   'EN'),
(3, 'Three', 'EN'),

(11, 'One.One',   'EN'),
(12, 'One.Two',   'EN'),
(13, 'One.Three', 'EN'),

(21, 'Two.One',   'EN'),
(22, 'Two.Two',   'EN'),
(31, 'Three.One', 'EN'),

(211, 'Two.One.One',   'EN'),
(212, 'Two.One.Two',   'EN'),
(213, 'Two.One.Three', 'EN');

-- lang_code = 'ES'
insert into of_category_lang (category_id, title, lang_code) values 
(0, 'Raíz', 'ES'),

(1, 'Uno',  'ES'),
(2, 'Dos',  'ES'),
(3, 'Tres', 'ES'),

(11, 'Uno.Uno',  'ES'),
(12, 'Uno.Dos',  'ES'),
(13, 'Uno.Tres', 'ES'),

(21, 'Dos.Uno',  'ES'),
(22, 'Dos.Dos',  'ES'),
(31, 'Tres.Uno', 'ES'),

(211, 'Dos.Uno.Uno',  'ES'),
(212, 'Dos.Uno.Dos',  'ES'),
(213, 'Dos.Uno.Tres', 'ES');