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

Question

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.

Answer 1

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)))

Answer 2

Here's a piece of code I have written that works for me.

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

        if 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)

            return (node_left, node_mid, node_right)

        elif node.left is None and node.right is None:
            return node.key

        elif node.left is None and node.right is not None:
            node_mid = node.key
            node_right = tree_to_tuple(node.right)
            node_left = None

            return (node_left, node_mid, node_right)

        elif node.left is not None and node.right is None:
            node_mid = node.key
            node_right = None
            node_left = tree_to_tuple(node.left)

            return (node_left, node_mid, node_right)

    else:
        print("It's not a tree")

Answer 3

Here is how I would do it:

def tree_to_tuple(node):
    if isinstance(node, TreeNode):
       return(tree_to_tuple(node.left), node.key, tree_to_tuple(node.right))
    else:return node

Answer 4

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


# instead of linking nodes one by one, we can represent nodes in the form of tuple
# and we can use recursion technique to automate linking process.  
  
def parse_tuple(data):

    # check if the parameter passed is of type tuple and it's length is 3 (left node, key, right node)
    if isinstance(data, tuple) and len(data) == 3:
        node = TreeNode(data[1])
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
    
    # if it is the leaf node(last node) and it is also == None, then assign node = None
    elif data is None:
        node = None
    
    # if it is a leaf node(last node) and not != to None, then assign node = current value
    else:
        node = TreeNode(data)
    
    return node


def tree_to_tuple(node):
    if isinstance(node, TreeNode):
        # check if left and right node are equal to None if so, then it means it has no child nodes
        # and simply just return key node
        if node.left is None and node.right is None:
            return node.key
        
        # use recursion to iterate through each sub tree and get the left , key and right nodes
        return (
            tree_to_tuple(node.left),
            node.key,
            tree_to_tuple(node.right)
        )
    # else simply return node
    else:
        return node

    
tree_tuple = ((1,3,None), 2, ((None, 3, 4), 5, (6, 7, 8)))
tree2 = parse_tuple(tree_tuple)
print(tree_to_tuple(tree2))


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