Python recursive function to search a binary tree-CodePudding

Very new at Python and I'm trying to understand recursion over a binary tree. I've implemented a very simple tree, which funnily enough maps English characters to binary (1's and 0's). I've only used a very simple structure because I am struggling to get my head round a more complex question that I've been set. I figure if I can get my head round my example then I should be able to go away and look at the question I've been set myself.

The following creates the class BinaryTree and an instance of this

class BinaryTree:
    """A rooted binary tree"""
    def __init__(self):
        self.root = None
        self.left = None
        self.right = None

def is_empty(testtree: BinaryTree) -> bool:
        """Return True if tree is empty."""
        return testtree.root == testtree.left == testtree.right == None

def join(item: object, left: BinaryTree, right: BinaryTree) -> BinaryTree:
    """Return a tree with the given root and subtrees."""
    testtree = BinaryTree()
    testtree.root = item
    testtree.left = left
    testtree.right = right
    return testtree

EMPTY = BinaryTree()
C = join('C',EMPTY,EMPTY)
D = join('D',EMPTY,EMPTY)
E = join('E',EMPTY,EMPTY)
F = join('F',EMPTY,EMPTY)
A = join('A',C,D)
B = join('B',E,F)
BINARY = join('START',B,A)

I visualise it as follows

Visualisation of the Binary tree

Now I'm trying to create a function that will take two inputs, a BinaryTree and a single character and the output will be the binary code for the corresponding letter (as an example, D = " 10 "). I'm outputting as a string rather than an integer. My function and test case as follows

# global variable
result = ''

#Convert binary to letter
def convert_letter(testtree: BinaryTree, letter: str) -> str:
    global result
    if testtree == None:
        return False
    elif testtree.root == letter:
        return True        
    else:  
        if convert_letter(testtree.left, letter) == True:
            result  = "1"
            return result
        elif convert_letter(testtree.right, letter) == True:
            result  = "0"
            return result
     
#Test
test = 'D' #Return '10'
convert_letter(BINARY, test)

And unfortunately that's where I'm hitting a brick wall. I had tried initialising an empty string within the function, but everytime it iterates over the function it overwrites the string. Any help greatly appreciated.

CodePudding user response：

I took the liberty of simplfying your code a bit let me know if you have any questions about how this works.

class node:
    """A rooted binary tree"""
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right

C = node('C')
D = node('D')
E = node('E')
F = node('F')
A = node('A',C,D)
B = node('B',E,F)
BINARY = node('START',B,A)

def convert_letter(n,letter):
    if n.value == letter:
        return "1" (convert_letter(n.left,letter) if not n.left is None else "") (convert_letter(n.right,letter)if not n.right is None else "")
    else:
        return "0" (convert_letter(n.left,letter) if not n.left is None else "") (convert_letter(n.right,letter)if not n.right is None else "")

def walk(n):
    return n.value (walk(n.left) if not n.left is None else "") (walk(n.right) if not n.right is None else "")

test = 'D'
print(convert_letter(BINARY, test))
print(walk(BINARY))

CodePudding user response：

This is not how I would personally structure an answer, but I think it most closely follows what you are attempting. The shortcoming of your answer only being that you are only returning one value, but kind of tracking two values. Note, I have taken the liberty of correcting:

BINARY = join('START',A,B)

Let's modify your method to return both a Boolean indicating if the letter was found as well as the indicator of the path.

def convert_letter2(testtree: BinaryTree, letter: str):
    if not testtree:
        return (False, "")

    if testtree.root == letter:
        return (True, "")

    test, val = convert_letter2(testtree.left, letter)
    if test:
        return (True, "1"   val)

    test, val = convert_letter2(testtree.right, letter)
    if test:
        return (True, "0"   val)

    return (False, "")

Then if we:

print(convert_letter2(BINARY, "D")[1])

We should get back "10"