Python - how do I return value from recurrsion-CodePudding

I am trying to run this code for search an element in a binary tree. It works well but I cannot return the value but can display it.

Here is my code:

def getNodeAddress(self, data):
        print(self._getNodeAddress(data, self.root))
    
def _getNodeAddress(self, data, root):
        if root:
            if root.data == data:
                print("<<<< ", root.data)
                return root
            self._getNodeAddress(data, root.left)
            self._getNodeAddress(data, root.right)

def _getNodeAddress(self, data, root, res):
        if root:
            if root.data == data:
                print("<<<< ", root.data)
                res = root
            self._getNodeAddress(data, root.left, res)
            self._getNodeAddress(data, root.right, res)
        print(res)
        return res

So in the above method, it traverses the tree to look for the value as the variable key, when it finds one it prints as in the line "print("<<<< ", root.data)", which does display as expected. But now the issue arises when I need to return the value to the parent method which is "getNodeAddress". I cannot print the value in the parent method. It just print "None" So my question is how do I return the value from a recursion.

I also tried the second approach as in the above code of the same method name, but still exactly the same the issue Any help would really be appreciated

CodePudding user response：

It looks like only the base case is actually returning anything. You need to add return statements in the non-base cases as well. For example:

def _getNodeAddress(self, data, root):
        if root:
            if root.data == data:
                print("<<<< ", root.data)
                return root
            res = self._getNodeAddress(data, root.left)
            if res is None:
                res = self._getNodeAddress(data, root.right)
            return res

CodePudding user response：

binary tree

This particular tree suffers bad performance as it performs linear (recursive) search in all branches and nodes. That means if you tree has 1,000,000 nodes, it could possibly take 1,000,000 recursions to find the data. If you implemented a proper binary search tree, you can guarantee the result in 20 recursions or less.

All that aside we can still implement find(t, data) for you tree, t -

def find(t, data):
  if not t:
    return None
  elif t.data == data:
    return t
  else:
    return find(t.left, data) or find(t.right, data)

Because recursion is a functional heritage, using it with functional style yields the best results. This means we avoid things like mutation, variable reassignment, and other side effects.

Note that this function does not return the path like your original function name suggests. If we want to get the exact path to the matched data in your tree, we can do so by adding a default path parameter -

def find(t, data, path = ()):
  if not t:
    return None
  elif t.data == data:
    return (*path, t)
  else:
    return find(t.left, data, (*path, t)) or find(t.right, data, (*path, t))

Notice how path starts as an empty tuple, (). Each recursive step appends the current tree node, t, to the path, until finally when data is found, the final node is appended to the path and returned.

binary search tree

A binary search tree allows you to traverse the tree in logarithmic time. This means a near instantaneous result can be provided whereas the same data in an ordinary (non-search) binary tree may grind your cpu to a halt.

# bst variant
def find(t, data):
  if not t:
    return None
  elif data < t.data:
    return find(t.left, data)
  elif data > t.data:
    return find(t.right, data)
  else:
    return t

We can write the path variant for the binary search tree as well -

# bst variant with path
def find(t, data, path = ()):
  if not t:
    return None
  elif data < t.data:
    return find(t.left, data, (*path, t))
  elif data > t.data:
    return find(t.right, data, (*path, t))
  else:
    return (*path, t)

more bst

If you would like to read more about binary search trees, I have some other answers on the topic -