Returning Array from Recursive Binary Tree Search

January 5, 2022

Hi I’ve made a simple Binary Tree and added a pre-order traversal method. After throwing around some ideas I got stuck on finding a way to return each value from the traverse_pre() method in an array.

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

    def add_child(self, val):
        if self.value:
            if val < self.value:
                if self.left == None:
                    self.left = BST(val)
                else:
                    self.left.add_child(val)
            else:
                if val > self.value:
                    if self.right == None:
                        self.right = BST(val)
                    else:
                        self.right.add_child(val)
        else:
            self.value = val

    def traverse_pre(self):
        if self.left:
            self.left.traverse_pre()
        print(self.value)

        if self.right:
            self.right.traverse_pre()


Tree = BST(5)
Tree.add_child(10)
Tree.add_child(8)
Tree.add_child(2)
Tree.add_child(4)
Tree.add_child(7)

Tree.traverse_pre()

How would I modify the traverse_pre() function to return an array consisting of the node values. Is there a good example of this process for me to understand this further, I’m a bit stuck on how values can be appended to an array within recursion.

>Solution :

Here is how I would do it – all branches return their lists of subelements.

In case a node has no subelements, it only returns its own value. Otherwise, it also contains elements from the children.

Extend adds all elements from the child node result list to the parent node result list.

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

    def add_child(self, val):
        if self.value:
            if val < self.value:
                if self.left == None:
                    self.left = BST(val)
                else:
                    self.left.add_child(val)
            else:
                if val > self.value:
                    if self.right == None:
                        self.right = BST(val)
                    else:
                        self.right.add_child(val)
        else:
            self.value = val

    def traverse_pre(self):
        results = []

        if self.left:
            results.extend(self.left.traverse_pre())

        results.append(self.value)

        if self.right:
            results.extend(self.right.traverse_pre())

        return results


Tree = BST(5)
Tree.add_child(10)
Tree.add_child(8)
Tree.add_child(2)
Tree.add_child(4)
Tree.add_child(7)

print(Tree.traverse_pre())