Recursive Binary Search Tree Implementation

How can I implement recursive methods in a Binary Search Tree class without a helper function? For example, my code below has add and preorder functions implemented with a helper function that I use to pass in the necessary parameters.

So far, everything I've tried to implement either of these without a helper has failed, for the code below I get:

preorder_with_helper:

[8, 4, 2, 6, 12, 10, 14]

preorder:

Traceback (most recent call last):
  File "/Users/briannakemp/Documents/coding/python/tree_recursion", line 7, in <module>
    class BST:
  File "/Users/briannakemp/Documents/coding/python/tree_recursion", line 37, in BST
    def preorder(self, root=self.root, data=[]) -> [int]:
NameError: name 'self' is not defined

What am I doing wrong? My code below:

class TreeNode:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None

class BST:
  def __init__(self):
    self.root = None

  def add_with_helper(self, value):
    def helper(root):
      if not root: return TreeNode(value)

      if value > root.value:
        root.right = helper(root.right)

      if value < root.value:
        root.left = helper(root.left)
      
      return root

    self.root = helper(self.root)

  def preorder_with_helper(self) -> [int]:
    def helper(root, data):
      if not root: return data

      data.append(root.value)
      if root.left: helper(root.left, data)
      if root.right: helper(root.right, data)

      return data

    return helper(self.root, [])

  def preorder(self, root=self.root, data=[]) -> [int]:
    if not root: return data

    data.append(root.value)
    if root.left: helper(root.left, data)
    if root.right: helper(root.right, data)

    return data




t = BST()
t.add_with_helper(8)
t.add_with_helper(4)
t.add_with_helper(12)
t.add_with_helper(6)
t.add_with_helper(2)
t.add_with_helper(10)
t.add_with_helper(14)

print(t.preorder_with_helper())
print(t.preorder())

CodePudding user response：

You can't pass self.root as a parameter - instead you can do this: print(t.preorder(t.root))

Also, i think your code is calling a 'helper' function which is not a attribute of the class BST -

    def preorder(self, root=None, data=[]) -> [int]:
        if not root: return data

        data.append(root.value)
        if root.left: self.preorder(root.left, data)
        if root.right: self.preorder(root.right, data)

        return data