Binary Tree in Python, control over the height

user_13656016 0
Viewed 51

I want to implement a Binary Tree in Python. I sumit my code. What I would like to do is to set the height of the Binary Tree with the variable L. But, when I implement the code, it seems that the code has created a Binary Tree that is greater than I expected. I arrive to this conclusion because when I set the height as 1 and I do print(node.right.right.right), I still get 1.

class Tree:
    def __init__(self,x,left=None,right=None):
      self.x=x
      self.left=left
      self.right=right 
    
    def one_tree(self,node):
        node=Tree(1)
        node.right=Tree(1)
        node.left=Tree(1)
        return node
        


node=Tree(1)
node=node.one_tree(node)
L=1

while L>0:
    node=node.one_tree(node)
    node.left=node
    node.right=node
    L=L-1

print(node.right.right.right.right)
tree height binary python
2 Answers

I found a problem with your code. one_tree method overwrites the argument node itself.

class Tree:
    def __init__(self, x, left=None, right=None):
        self.x = x
        self.left = left
        self.right = right 
    
    def one_tree(self, node):
        node = Tree(1) # This assignment statement overwrites the argument 'node'.
        node.right = Tree(1)
        node.left = Tree(1)
        return node

one_tree method gets an argument node but the first line of this method overwrites it like this node = Tree(1). Whatever the method gets as an argument, the method always has a new instance of Tree as node variable.

user_41643980

Several issues:

  • one_tree doesn't use the node that you pass as argument, so whatever you pass to it, the returned tree will always have 3 nodes (a root with 2 children).

  • one_tree is a method that doesn't use self, so it really should be a class method, not an instance method

  • If the intended algorithm was to add a level above the already created tree, and have the new root's children reference the already existing tree, then you would need to only create one node, not three, and let the two children be the given node.

  • Not a problem, but your loop is not really the "python way" to loop L times. Use range instead.

This means your code could be this:

class Tree:
    def __init__(self, x, left=None, right=None):
        self.x = x 
        self.left = left
        self.right = right


node = Tree(1)
L = 1
for _ in range(L):
    node = Tree(1, node, node)

Now you should still be careful with this tree, as it only has L+1 unique node instances, where all "nodes" on the same level are actually the same node instance. All the rest are references that give the "impression" of having a tree with many more nodes. Whenever you start mutating nodes in that tree, you'll see undesired effects.

If you really need separate node instances for all nodes, then the algorithm will need to be adapted. You could then use recursion:

def create(height):
    if height == 0:  # base case
        return Tree(1)
    return Tree(1, create(height-1), create(height-1))

L = 1
node = create(L)
user_54598390
Related