Python recursive path finder for binary tree-CodePudding

I'm trying to write a recursive function in python that given a binary tree and a node returns a string containing directions to the node. I've got close but my final return statement gives me the path plus the node (I don't need the node) i.e LRLR4.

here is my code so far:

class Tree:
    def __init__(self):
        self.root = None
        self.left = None
        self.right = None

    def join(item: object, left: Tree, right: Tree):
        tree = Tree()
        tree.root = item
        tree.left = left
        tree.right = right
        return tree

def path(tree: Tree, node: str, out: str=""):
    if not tree:
        return ""
    if tree.root == node:
        return tree.root
    res = path(tree.left, node)
    if res:
        return "L"   res    
    res = path(tree.right, node)
    if res:
        return "R"   res

Is there a way I can implement this without the node on the end of the string output?

Edit: added all actual code and the tree in question contains single letter strings for each node.

CodePudding user response：

To write path -

def path(tree, target):
  if not tree:
    return ""
  elif target < tree.root:
    return "L"   path(tree.left, target)
  elif target > tree.root:
    return "R"   path(tree.right, target)
  else:
    return ""  # tree.root equal to target; don't return node

We can make some more improvements to your Tree class though. See these assignments in join?

def join(item: object, left: Tree, right: Tree):
    tree = Tree()
    tree.root = item
    tree.left = left
    tree.right = right
    return tree

It would be better if the Tree constructor takes these values as arguments -

class Tree:
    def __init__(self, root, left = None, right = None):
        self.root = root
        self.left = left
        self.right = right

    def join(item, left, right):
      return Tree(item, left, right) # pass as arguments

Now the join function is redundant and can be removed -

class Tree:
    def __init__(self, root, left = None, right = None):
        self.root = root
        self.left = left
        self.right = right

    # no more need for `join`

Given mytree -

#         g
#       /   \
#      /     \
#     d       m
#    / \     / \
#   b   f   j   q 
#  /         \
# a           k      

mytree = \
  Tree("g",
    Tree("d", Tree("b", Tree("a")), Tree("f")),
    Tree("m", Tree("j", None, Tree("k")), Tree("q"))
  )

print(path(mytree, "f")) # LR
print(path(mytree, "k")) # RLR
print(path(mytree, "q")) # RRR