How do i create a function to convert a binary tree to a tuple?-CodePudding

i came across this question where i was tasked to convert a tuple into binary tree and then convert binary tree back to tuple and return both tree and tuple. i was able to convert the tuple into the tree but i failed to create a function to do the reverse. i am just a begineer trying learn data structures.

the parse_tuple function here is used to parse over a tuple to create a binarytree which works fine.

please help me fix my tree_to_tuple function. any insights or tips to fix the logic would be great.

thanks

#used for creating binary tree
class TreeNode:
    
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

#used to parse over the tuple to create a bianry tree
def parse_tuple(data):
    
    if isinstance(data, tuple) and len(data) == 3:
        
        node = TreeNode(data[1])
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
        
    elif data is None:
        node = None
    
    else:
        node = TreeNode(data)
    
    return node

#doesnt work
def tree_to_tuple(node):
    if isinstance(node, TreeNode) and node.left is not None and node.right is not None:
        node_mid = node.key
        node_left = tree_to_tuple(node.left)
        node_right = tree_to_tuple(node.right)
    
    elif node.left is None:
        node_left = None
        
    else:
        node_right = None
        
    return (node_left, node_mid, node_right)

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

tree2 = parse_tuple(tree_tuple)

tree_tuple2 = (1, 2, 3)
tree = parse_tuple(tree_tuple2)
print(tree_to_tuple(tree2))

and this is the error i am getting if i try to use tree_to_tuple

File "main.py", line 45, in tree_to_tuple return (node_left, node_mid, node_right) UnboundLocalError: local variable 'node_left' referenced before assignment.

CodePudding user response：

You were close but your tests are a bit messy.

Here is a patch:

def tree_to_tuple(node):
    if isinstance(node, TreeNode):

        #  special case if the tree has no left and no right sub-tree
        if node.left is None and node.right is None:
            return node.key

        return (
            tree_to_tuple(node.left),
            node.key,
            tree_to_tuple(node.right)
        )
    raise ValueError('this is not a tree')

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

tree2 = parse_tuple(tree_tuple)

tree_tuple2 = (1, 2, 3)
tree = parse_tuple(tree_tuple2)
print(tree_to_tuple(tree2))

Output:

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