Search full path for a node

Question

Lets say I have an array of Tags, where tags are:

final class Tag {
  let title: String
  let tags: [Tag] // A tag can have 'n' children tags.
}

let myTags = [Tags]() // Filled with data

Given a Tag, I want to to get in order the full path of its parents. So for example, tag A142, should return [A, A1, A14]. (Invented titles, they don't store this data, but it will be helpful to visualize what I'm searching for)

Tried different versions but I'm unable to get recursion going on:

func searchPath(for tag: Tag, in data: [Tag], path: [Tag]) -> [Tag]? {
    for child in data {
        print(child.title)
        if child.tags.isEmpty && child == tag {
            return path
        } else if !child.tags.isEmpty {
            return searchPath(for: tag, in: child.tags, path: path + [child])
        } else {
        }
    }
    return []
}

A more detailed example would be:

private let mock: [Tag] = {
    [
        .init(title: "Car", tags: [
            .init(title: "Porsche", tags: []),
            .init(title: "BMW", tags: [])
        ]),
        .init(title: "Flight", tags: [
            .init(title: "A1", tags: [
                .init(title: "A11", tags: []),
                .init(title: "A12", tags: [
                    .init(title: "A121", tags: []),
                    .init(title: "A122", tags: [])
                ])
            ]),
            .init(title: "A2", tags: [])
        ])
    ]
}()

So searching for the tag A122 in "mock", should return tags for "Fligh", "A1, "A12".

Joakim Danielson · Answer

This solution consists of two functions because I was originally working with a tree solution before I understood that the input was an array.

First the main one

public func searchPath(for tag: Tag, in data: [Tag]) -> [Tag] {
    var result = [Tag]()
    for item in data {
        searchPath(for: tag, in: item, path: &result)
        if result.isEmpty == false { break}
    }
    return result
}

and then the recursive one that does the actual searching and builds up the path

private func searchPath(for tag: Tag, in parent: Tag, path: inout [Tag]) {
    guard parent.tags.isEmpty == false else { return }

    path.append(parent) // always add the parent

    if parent.tags.contains(tag) { return } // we have a match, current path is the end result
    for child in parent.tags where child.tags.isEmpty == false {
        searchPath(for: tag, in: child, path: &path)
        if path.isEmpty == false { return } // we have a path
    }

    path = [] //No match if we get here, clear the path.
}

This solution require that Tag conforms to Equatable

Search full path for a node

1 Answers