CODEWITHSUNDEEP
pythontree
Petur Ulev
Petur Ulev

Reputation: 97

Get i-th element in jth level in binary tree Python

The methods I wrote are getNode and helper. For some reason it does not work. Here is the code.

Class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def helper(self, level, ind, arr):
        if level == 0:
            arr.append(self)
        else:
            if self.left:
                self.left.helper(level-1, ind, arr)
            if self.right:
                self.right.helper(level-1, ind, arr)

        return arr[ind]

    def getNode(self, level, ind):
        arr = []
        return self.helper(level, ind, arr)





# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print(self.data),
        if self.right:
            self.right.PrintTree()

root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.insert(7)
root.insert(13)
root.PrintTree()

a = root.getNode(2, 2).data
print('Answer is: ', a)

I get the following error after I run it:

File "btree.py", line 33, in helper
    return arr[ind]
IndexError: list index out of range

Upvotes: 2

Views: 102

Answers (2)

Josh Bothun
Josh Bothun

Reputation: 1344

It looks basically correct, the problem is that your helper function is recursively building up an array, but on each iteration its trying to return the i-th element before it has finished appending to the array:

return arr[ind]

Instead you should have helper return nothing and simply fill the given array, and then modify getNode to be:

def getNode(self, level, ind):
    arr = []
    self.helper(level, ind, arr)
    return arr[ind]

Upvotes: 2

Samwise
Samwise

Reputation: 71454

It looks like you're passing in an empty array for arr and then trying to access its 3rd element (after doing some recursive calls that may or may not result in adding some things to arr -- I expect that if any of those calls do add some elements, they don't add enough).

I think you're trying to do too many things at once -- rather than have your recursive helper function try to get the Nth item from the array (before it's finished being built), I'd focus on having the helper just be in charge of adding things to the array in the correct order, and then have getNode inspect the array after all the helper calls have finished.

Upvotes: 0

Related Questions