CODEWITHSUNDEEP
pythonrecursionbinary-tree
Peter
Peter

Reputation: 185

Right way to construct a binary tree?

Suppose we have a class BinaryTree defined as follows (which cannot be modified):

class BinaryTree:
    def __init__(self, value = None):
        self.value = value
        if self.value is not None:
            self.left_node = BinaryTree()
            self.right_node = BinaryTree()
        else:
            self.left_node = None
            self.right_node = None

And I have a stack, which consists of numbers and '+'s, e.g,

stack = ['1', '2', '+', '3', '4', '5', '+', '+', '+']

Now I want to a construct the binary tree. The rule is as follows: starting from right to left, the root is '+'. Then if the character is '+', extend the branch, else, we add numbers from left_node to right_node.

By the order I pop the last element in my list, the detailed illustration of the process is as follows:

t = BinaryTree('+')
t.left_node = BinaryTree('+')
t.left_node.left_node = BinaryTree('+')
t.left_node.left_node.left_node = BinaryTree('5')
t.left_node.left_node.right_node = BinaryTree('4')
t.left_node.right_node = BinaryTree('3')
t.right_node = BinaryTree('+')
t.right_node.left_node = BinaryTree('2')
t.right_node.right_node = BinaryTree('1')

So eventually the visual representation of the tree is something like thisvisual representation of the tree

I know I need to approach this problem using recursion and control structure, but I am not sure how this can be applied to adding nodes in the tree.

If anything needs to be clarified please let me know and any help will be appreciated.

Upvotes: 0

Views: 52

Answers (1)

Marc Z
Marc Z

Reputation: 116

I would do the following:

  • define a function that builds a node using a list and returns what's left of the list:

    def noding(l):

    t = BinaryTree(l[-1])
if l[-1] == '+':
    left, rest = noding(l[:-1])
    t.left_node = left
    right, rest = noding(rest)
    t.right_node = right
    return t, rest
if l[-1] != '+':
    return t, l[-1]

It's a bit raw, I don't have time to really think it thoroughly, especially with the handling of None.

Edit : don't return None, but return l[:-1] like previously.

Upvotes: 1

Related Questions