unable to implement recursion in binary tree-CodePudding

I just learned how to create a balanced binary tree and how to access them. For example, if this is my tree: date = ((1,3,None),2,((None,3,4),5,(6,7,8))) I can create it by given code:

class tree:
    def __init__(self,key):
        self.key = key
        self.right = None
        self.left = None
node_0 = tree(2)
node_1 = tree(3)
node_2 = tree(5)
node_3 = tree(1)
node_4 = tree(3)
node_5 = tree(7)
node_6 = tree(4)
node_7 = tree(6)
node_8 = tree(8)
#connecting
node_0.left = node_1
node_0.right = node_2
node_0.left.left = node_3
node_0.right.left = node_4
node_0.right.right = node_5
node_0.right.left.left = node_6
node_0.right.right.left = node_7
node_0.right.right.right = node_8
#accesing
node_0.right.right.right.key

But this method is very inefficient and lengthy so I tried recursion in place of that:


def parse_tuple(data):
    
    if isinstance(data,tuple) and len(data)==3:
        node = (data[1])
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
    elif data is None:
        node = None
    else:
        node=(data)
    return node

so my idea is access data = ((1,3,None),2,((None,3,4),5,(6,7,8))) , by passing into a function but there's a problem the function work well's till node.left = parse_tuple(data[0]). Basically here's what's going on

18:10:41.43 >>> Call to parse_tuple in File "C:\Users\muzza\AppData\Local\Temp\ipykernel_17864\3153403204.py", line 4
18:10:41.43 ...... data = ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))
18:10:41.43 ...... len(data) = 3
18:10:41.43    4 | def parse_tuple(data):
18:10:41.43    6 |     if isinstance(data,tuple) and len(data)==3:
18:10:41.43    7 |         node = (data[1])
18:10:41.43 .............. node = 2
18:10:41.43    8 |         node.left = parse_tuple(data[0])
    18:10:41.44 >>> Call to parse_tuple in File "C:\Users\muzza\AppData\Local\Temp\ipykernel_17864\3153403204.py", line 4
    18:10:41.44 ...... data = (1, 3, None)
    18:10:41.44 ...... len(data) = 3
    18:10:41.44    4 | def parse_tuple(data):
    18:10:41.44    6 |     if isinstance(data,tuple) and len(data)==3:
    18:10:41.44    7 |         node = (data[1])
    18:10:41.44 .............. node = 3
    18:10:41.44    8 |         node.left = parse_tuple(data[0])
        18:10:41.44 >>> Call to parse_tuple in File "C:\Users\muzza\AppData\Local\Temp\ipykernel_17864\3153403204.py", line 4
        18:10:41.44 ...... data = 1
        18:10:41.44    4 | def parse_tuple(data):
        18:10:41.44    6 |     if isinstance(data,tuple) and len(data)==3:
        18:10:41.44   10 |     elif data is None:
        18:10:41.45   13 |         node=(data)
        18:10:41.45 .............. node = 1
        18:10:41.45   14 |     return node
        18:10:41.45 <<< Return value from parse_tuple: 1
    18:10:41.45    8 |         node.left = parse_tuple(data[0])
    18:10:41.46 !!! AttributeError: 'int' object has no attribute 'left'
    18:10:41.46 !!! When getting attribute: node.left
    18:10:41.46 !!! Call ended by exception
18:10:41.46    8 |         node.left = parse_tuple(data[0])
18:10:41.47 !!! AttributeError: 'int' object has no attribute 'left'
18:10:41.47 !!! When calling: parse_tuple(data[0])
18:10:41.47 !!! Call ended by exception



I tried to fix the issue but I can't think of any option available. I want to access the data that I've passed, just like the first method above mentioned. I've come across many recursion techniques to implement binary trees but I want correction in this code so that I can know my mistake.

CodePudding user response：

The problem is that your code does not call the tree constructor. Your node should be an instance of that class, yet you merely assign the key to node.

So change node = (data[1]) to node = tree(data[1]) and node=(data) to node=tree(data)

CodePudding user response：

Fixing your `parse_tuple` recursive function

Your function parse_tuple is almost correct, but you need to call tree() at each recursive call to create all the nodes.

def parse_tuple(data, node=None):
    if isinstance(data, tuple) and len(data) == 3:
        l, k, r = data
        node = tree(k)
        node.left = parse_tuple(l)
        node.right = parse_tuple(r)
    elif data is None:
        node = None
    else:
        node = tree(data)
    return node

parse_tuple( ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8))) )

Tree creation using `Tree.init`

There is a much simpler option.

Modify your method __init__ so that it accepts right and left arguments.

Instead of:

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

I suggest to use instead:

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

This way, you can create the full tree directly:

node0 = Tree(2, Tree(3, Tree(1)), Tree(5, Tree(3, Tree(4)), Tree(7, Tree(6), Tree(8))))

Or perhaps more lisibly with some indentation:

node0 = Tree(2,
             Tree(3,
                  Tree(1)),
             Tree(5,
                  Tree(3, Tree(4)),
                  Tree(7, Tree(6), Tree(8))))

Fixing your parse_tuple recursive function

Tree creation using Tree.__init__

Fixing your `parse_tuple` recursive function

Tree creation using `Tree.init`