Recursive function does not return array in python-CodePudding

I'm writing a simple code that returns the path to the destination node in BST.

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)

After defining the tree;

p = 2
q = 8

def pathFind(path, cur, node): # path : path the function walked throug so far
                               # cur : current node
                               # node : destination node's value 
  
  #print(f'current node value is {cur.val}')
  #print(path)
  ## ending condition ##
  if cur.val == node: # If we reach the destination node
    return path
  
  elif cur.val < node and cur.right != None : 
    # 'if cur.right != None:' line is useless since the problem guarantees the existence of destination value in BST 
    path.append(cur)

    return pathFind(path, cur.right, node)
  elif cur.val > node and cur.left != None: # cur.val > node:
    path.append(cur)
    return pathFind(path, cur.left, node)
  else:
    return None

path_p = pathFind([root], root, p)

I checked that my function reaches the destination and record the path toward it without any problem, but the last line - path_p = pathFind([root], root, p) doesn't work.

Anyone could help?

CodePudding user response：

In function pathFind(), the path is returned only by the execution where the tested node contains the target value. The (all) previous executions discard that return value. Fix it by putting return before the recursive calls.

CodePudding user response：

Try below code to find the path for a target node

def pathFind(path, node, target):
    if node == None:
        return
    else:
        path.append(node.val)
        if node.val == target:
            return path
        elif node.val < target and node.right != None:
            return pathFind(path, node.right, target)
        elif node.val > target and node.left != None:
            return pathFind(path, node.left, target)
        else:
            return None

print(pathFind([], root, 9))

output

[6, 8, 9]