I try to write my own tree component. A tree node renders as a div containing child components of the tree component, for example:

<my:tree id="extendedTree"
         value="#{controller.rootNode}"
         var="node">
    <h:outputText id="xxx" value="#{node.name}" />
    <h:commandLink value="Test" actionListener="#{controller.nodeSelectionActionListener}" />
</my:tree>

So far, so good - everything works as expected, but the h:outputText gets the same id repeatedly.
So I had my component implement javax.faces.NamingController, overwriting getContainerClientId():

@Override
public String getContainerClientId(FacesContext context) {
    String clientId = super.getClientId(context);
    String containerClientId = clientId + ":" + index;
    return containerClientId;
}

index is set and updated during iteration over the nodes. But getContainerClientId() is called only once for every children (not for every iteration and every children, as I would expect). That causes every child id to be prefixed with the same container id:

form:treeid:0:xxx

Same thing for overwriting getClientId().

What did I miss?

The answer is hidden in the bottom of chapter 3.1.6 of JSF 1.2 specification:

3.1.6 Client Identifiers

...

The value returned from this method must be the same throughout the lifetime of the component instance unless setId() is called, in which case it will be recalculated by the next call to getClientId().

In other words, the outcome of getClientId() is by default cached by the JSF component as implemented in UIComponentBase#getClientId() (see also the nullcheck at line 275 as it is in Mojarra 1.2_15) and this cache is resetted when the UIComponentBase#setId() is called (see also line 358 as it is in Mojarra 1.2_15). As long as you don't reset the cached client ID, it will return the same value on every getClientId() call.

So, while rendering the children in encodeChildren() implementation of your component or the renderer which shall most probably look like this,

for (UIComponent child : getChildren()) {
    child.encodeAll(context);
}

you should for every child be calling UIComponent#setId() with the outcome of UIComponent#getId() to reset the internally cached client ID before encoding the child:

for (UIComponent child : getChildren()) {
    child.setId(child.getId());
    child.encodeAll(context);
}

The UIData class behind the <h:dataTable> implementation does that by the way also (see line 1382 as it is in Mojarra 1.2_15). Note that this is not JSF 1.x specific, the same applies on JSF 2.x as well (and also on UIRepeat class behind Facelets <ui:repeat>).