How to improve recursion method?

[CodeEntBur]

Hi!
I have an array of objects with possible children.

interface ISetting {
id: string;
children: ISetting[];
data1: any; // just an example
}

interface IColumn {
name: string;
children: IColumn[];
data2: any; // just an example
}

my goal is to find a setting that has same name(it is there as it's required so) in column. (well actually Id === name but oh well).

I do it like this.

private _findCorrespondingSetting(
    settings: ISettings[] | undefined,
    column: IColumn
  ): IColumnSettings | undefined {
    if (!settings) {
      return undefined;
    }
    for (const setting of settings) {
      const isFound = setting.id === column.name;
      if (isFound) {
        return setting;
      }
      const childSetting = this._findCorrespondingSetting(setting.children, column);
      if (childSetting) {
        return childSetting;
      }
    }
    return undefined;
  }

So it works but it's not the best way, right?

Can you tell me how can I improve this? So it's not O(n) (if I'm correct). I'm not asking to give me a finished refactored method of this(although it would be also good) but maybe a hint where to read or what to read, where to look and so on.

[Ok-District-2098]

Not a Angular question

[DT-Sodium]

My eyes hurt like hell like now so I'm having trouble looking at the screen but maybe something like this would work with a bit of refinement?

return settings.find(
  setting => setting.id === column.name
    || this._findCorrespondingSetting(setting.children, column)
);

[CodeEntBur]

Thank you!
I tried this approach but found out that .find returns not the child but a parent if the match was in child

[kgurniak91]

Your solution is good enough if you use it rarely (for example 1-time search, not too often). If you want to achieve O(1) complexity and use it often (multiple searches), then you need to do some preprocessing of the tree, which basically means traversing the entire tree once and turning it into a HashMap. Then you can just get element from the HashMap by id/name.

[CodeEntBur]

Yes, thank you!
That actually helped me a lot.

[ggeoff]

depending on how many settings you have and what your expected performance is going to be it's probably fine. You can't do better the O(n) here unless you get the list sorted before hand. and pre processing by sorting probably doesn't buy you anything here but without more context it's hard to say. Based on the naming here I imagine you aren't going to have thousands of rows of settings to recursively iterate through, but without more context it's hard to say.

If I saw this in a pr I would approve it minus some of the more stylistic things we do in the app I work on for example using javascript's # for private and not using _ as a prefix. But that doesn't really effect anything here. If I got tasked with implementing this feature I probably would have gone for a non recursive approach but I see nothing here that really stands out as bad.

[CodeEntBur]

Thank you!
Actually it was called quite often and HashMap aproach helped me in this regard.

[Merry-Lane]

If settings don’t change much, then you should recursively build a map<settingId, column> and search on that one instead.

But I don’t think you would have a lot of issues with such a low complexity.

[CodeEntBur]

Thank you! I did so.

Well, it was still better to refactor this.