2

I want to define a function which returns a list of the tree node values. The list is in level order (top to bottom, left to right), if a child is missing then in its location, "None" is inserted.

This is the Binary Tree implementation

class BinaryTree:

def __init__(self, data, left = None, right = None):

    self.left = left
    self.right  = right

def insert_left(self, data):
    self.left = BinaryTree(data, left=self.left)  

def insert_right(self, data):
    self.right = BinaryTree(data, right=self.right)

def set_value(self, val):
    self.key = val

def get_value(self):
    return self.key

def create_string(self, indent):
    string = str(self.key) + '---+'
    if self.left:
        string += '\n(l)' + indent + self.left.create_string(indent + '    ')
    if self.right:
        string += '\n(r)' + indent + self.right.create_string(indent + '    ')
    return string

def __str__(self):
    return self.create_string('  ')

def return_list(self, templist):
    templist.append(self.key)
    if self.left is None:
        templist.append(None)
    else:
        self.left.return_list(templist)
    if self.right is None:
        templist.append(None)
    else:
        self.right.return_list(templist)

def main():    
    tree = BinaryTree(3) 
    tree.insert_left(29)
    tree.insert_right(4)
    right = tree.get_right_subtree()
    left = tree.get_left_subtree()
    left.insert_left(26)
    right.insert_right(2)
    right2 = right.get_right_subtree()
    right2.insert_left(9)
    templist = []
    tree.return_list(templist)
main()
Improve this question

4 Answers 4

Reset to default
1

Adding the entire .py file If you run this it should work

from collections import deque

class BinaryTree:
    def __init__(self, data, left = None, right = None):
        self.key = data
        self.left = left
        self.right  = right

    def insert_left(self, data):
        self.left = BinaryTree(data, left=self.left)  

    def insert_right(self, data):
        self.right = BinaryTree(data, right=self.right)

    def get_left_subtree(self):
        return self.left

    def get_right_subtree(self):
        return self.right

    def set_value(self, val):
        self.key = val

    def get_value(self):
        return self.key

    def create_string(self, indent):
        string = str(self.key) + '---+'
        if self.left:
            string += '\n(l)' + indent + self.left.create_string(indent + '    ')
        if self.right:
            string += '\n(r)' + indent + self.right.create_string(indent + '    ')
        return string

    def __str__(self):
        return self.create_string('  ')

    def return_list(self, templist):
        templist.append(self.key)
        if self.left is None:
            templist.append(None)
        else:
            self.left.return_list(templist)
        if self.right is None:
            templist.append(None)
        else:
            self.right.return_list(templist)


def return_b_list(tree,templist,queue):
    if tree is None:
        return;
    queue.append(tree)
    while len(queue) !=0:
        node = queue.popleft()
        if node is None:
            templist.append(None)
        else:
            templist.append(node.key)
            queue.append(node.left)
            queue.append(node.right)




def main():    
    tree = BinaryTree(3) 
    tree.insert_left(29)
    tree.insert_right(4)
    right = tree.get_right_subtree()
    left = tree.get_left_subtree()
    left.insert_left(26)
    right.insert_right(2)
    right2 = right.get_right_subtree()
    right2.insert_left(9)
    templist = []
    queue = deque() # you should do a from collections import deque
    return_b_list(tree,templist,queue)
    print tree.create_string(' ')
    print templist

main()
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

you should pass a empty list to this function

def return_list(self, templist):
    templist.append(self.key)
    if self.left is None:
        templist.append(None)
    else:
        self.left.return_list(templist)
    if self.right is None:
        templist.append(None)
    else:
        self.right.return_list(templist)

after you call this method templist will have the list that you want

Improve this answer

15 Comments

I was going to use this to call tree =BinaryTree(2) tree.insert_left(31) tree.insert_right(5) right = tree.get_right_subtree() left = tree.get_left_subtree() left.insert_left(27) right.insert_right(1) right2 = right.get_right_subtree() right2.insert_left(7)
But return_list has two parameters so what would i use for my second parameter when calling , like return_list(tree,...)
No this will be a method of class so you call as tree.retrun_list(templist). where templist is an empty list.
i get this error when i call it AttributeError: 'BinaryTree' object has no attribute 'return_list'
you should add this method to your class. this will be member method
|
0

If you are exactly looking for breadth first search then this method might help

  def return_b_list(tree,templist,queue):
    if tree is None:
        return;
    queue.append(tree)
    while len(queue) !=0:
        node = queue.popleft()
        if node is None:
            templist.append(None)
        else:
            templist.append(node.key)
            queue.append(node.left)
            queue.append(node.right)

How to call? ( this method need not be part of the class)

def main():    
    tree = BinaryTree(3) 
    tree.insert_left(29)
    tree.insert_right(4)
    right = tree.get_right_subtree()
    left = tree.get_left_subtree()
    left.insert_left(26)
    right.insert_right(2)
    right2 = right.get_right_subtree()
    right2.insert_left(9)
    templist = []
    queue = deque() # you should do a from collections import deque
    return_b_list(tree,templist,queue)
    print templist
Improve this answer

8 Comments

it doesnt seem to work it doesnt give level order traversal
what is the output you are getting
[2, 29, 26, None, None, None, 4, None, 2, 9, None, None, None]
but it should be this: [2, 29, 4, 26, None, None, 2, None, None, None, None, None, None, 9, None]
I'm trying to avoid putting the function in the class, and just have it seperate from the class ?
|
0

This is not a answer but just wanted to add the result that i am getting and the clarification

$ python binarayTree.py
3---+
(l) 29---+
(l)     26---+
(r) 4---+
(r)     2---+
(l)         9---+

[3, 29, 4, 26, None, None, 2, None, None, 9, None, None, None]

Here is the explanation of result list

first level 3
second level 29,4
third level 26, None, None ,2
fourth level None, None,9, None, None, None
Improve this answer

5 Comments

your getting this through the def return_list function you provided ?
I dont understand why I'm getting a different output. I changed the code abit to take out self, and added a tree parameter instead
something must be different because I copy pasted everything and my outcome is different to yours :/
No it is not from def return_list it is from return_b_list
Let me add the py file

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.