Title: Right way to construct a binary tree?
Tags: python;recursion;binary-tree
Question: 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 this
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.
Comment: This looks like a standard introductory data structures question. If it is homework, you might find [this Meta Stack Overflow topic](https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions) useful for asking this question.

Comment: Since it's homework, which of the Algorithms texts are you using (or have on hand from a previous class)? Cormen? Sedgewick?

Comment: Hi Matthew, thank you for your reminder. Yes, it is indeed part of the homework that I am stuck with at the moment.

Comment: Oh we don't have a textbook, the lecturer explained the binary tree but this challenge requires rather knowledge on recursion

Here is the accepted answer: 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.
Comment for this answer: Thank you Marc for your tip, it really helped me as I was stuck with the idea that I have to call the recursive function after my return statement. Your answer was great, however, just for the purpose of this question, I would slightly change l[-1] into l.pop() as I am progressing the list. This really helped me thank you very much!


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 4, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2017:00:05/26/17', 'FavoriteCount': 1.0, 'PostTypeId': 1, 'Tags': '<python><recursion><binary-tree>', 'Title': 'Right way to construct a binary tree?', 'ViewCount': 46, 'id': 44204907, 'user_AboutMe': None, 'user_AccountId': 10585678.0, 'user_DisplayName': 'Peter', 'user_Reputation': 185.0, 'user_Views': 39.0, 'user_id': 7798124.0}}