CODEWITHSUNDEEP
pythonrecursionbinary-tree
mrQWERTY
mrQWERTY

Reputation: 4149

Recursively obtaining path to node in binary tree

I am having issues getting the path to a node in a binary tree. Specifically, I don't know how to pop elements off of the stack as I return from a stack frame.

def getPath(self, target):

    stack = []

    def _getPath(head):
        nonlocal stack
        nonlocal target

        stack.append(head)

        if head.value == target:
            return stack
        if head.left is not None:
            _getPath(head.left)
        if head.right is not None:
            _getPath(head.right)

    _getPath(self.root)

    return stack

Currently, the stack will contain all of the elements in the tree.

Upvotes: 0

Views: 1190

Answers (1)

Pachelbel
Pachelbel

Reputation: 533

A problem here is: the information of when the target is found has to be propagated back to the called instances of getPath. The construction of the stack is kind of a "side effect" of the finding. Therefore I propose you return a boolean value in getPath, that is True iff the target was found within the subtree currently investigated. Then we know we have to attach a value to the "stack":

def getPath(self, target):

    stack = []

    def _getPath(head):
        nonlocal stack
        nonlocal target
        if head.value == target:
            stack.append(head)
            return True
        for child in (head.left, head.right):
            if child is not None:
                if  _getPath(child):
                    stack.append(head)
                    return True
        return False


    _getPath(self.root)
    return reversed(stack)

Upvotes: 3

Related Questions