Finding Path to a Node - Tree with multiple children

CodeGorilla 0
Viewed 31

I have been scratching my head to find a solution to this problem. I am not very good with data structures and it seems that my brain melts a little whenever I have to do anything to do with trees.

Suppose we have a Node():

Node(name: String, children: List<Node>?)

And we have a tree made up of these nodes:

var node6 = Node("6", null)
var node5 = Node("5", null)
var node4 = Node("4", null)
var node3 = Node("3", listOf(node5, node6))
var node2 = Node("2", null)
var node1 = Node("1", listOf(node2, node3, node4))

What approach could I take to find the path (stored) to node6 while only having the root available?

Thank you kindly for any advice you could offer!

Solution as per JayC667's guidance:

fun recursiveCheck(
    nodeA: Node,
    nodePath: Stack<Node>,
    nodeToFind: String
) : Boolean {
    // Push param node to stack
    nodePath.push(nodeA)

    // Check param node
    if(nodeA.name == nodeToFind) {
        return true
    }

    if(nodeA.children != null) {
        // Iterate over all children using recursive check
        for(child in nodeA.children!!) {
            // child found as param node
            if(recursiveCheck(child, nodePath, nodeToFind)) return true
        }
    }

    // Did not find node, popping off stack
    nodePath.pop()
    return false
}
tree data-structures java kotlin
1 Answers

Simple. If the node only exists once in the tree and is reachable from the root, of course.

Use a Stack as node path stack:

  1. Starting method: create stack, call recursive check method, params: (root node, node path stack, node to find)
  2. Recursive Check method: push param node to stack, check param node, iterate over all children + for each child call recursive check method. If child was found as param node or in the subcalls, immediately return true (and return)
  3. each time you leave the recursive check method (at the end, if you have NOT found the node), pop the current element off the stack.
  4. if in the starting method the Recursive Check method has returned true, your node path will lie on the stack
JayC6670
Related