Binary Search Tree traversal using recursion to store in JSON-CodePudding

I am trying to write a function to traverse a tree and store the values in a dictionary. I am using a dictionary because I want the structure of the tree to be preserved in JSON format. But the return only gives me the first level of the tree. I have inserted the nodes using an insert function. This is my attempt to understand recursion in a tree.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None 
        self.right = None

def __str__(self):
    return str(self.data)

class BinarySearchTree:
    def __init__(self):
        self.root = None

# Return the BST object in dictionary format
def __str__(self):
    return str(self.__dict__)

def traverse(self, current_node):
    tree = {'root': current_node.data}
    print(tree)
    if current_node.left is not None:
        tree.update({'left': current_node.left.data})
        print(tree)
        self.traverse(current_node.left)
    if current_node.right is not None:
        tree.update({'right': current_node.right.data})
        print(tree)
        self.traverse(current_node.right)
    return tree

My Output:
     __10_____           
    /         \          
   _5_       20_________ 
  /   \     /           \
 _3   7    15    ______73
/  \ /    /     /        
1  4 6   12    25___     
 \                  \    
 2                 30_   
                  /   \  
                 27  35  
{'root': 10}
{'root': 10, 'left': 5}
{'root': 5}
{'root': 5, 'left': 3}
{'root': 3}
{'root': 3, 'left': 1}
{'root': 1}
{'root': 1, 'right': 2}
{'root': 2}
{'root': 3, 'left': 1, 'right': 4}
{'root': 4}
{'root': 5, 'left': 3, 'right': 7}
{'root': 7}
{'root': 7, 'left': 6}
{'root': 6}
{'root': 10, 'left': 5, 'right': 20}
{'root': 20}
{'root': 20, 'left': 15}
{'root': 15}
{'root': 15, 'left': 12}
{'root': 12}
{'root': 20, 'left': 15, 'right': 73}
{'root': 73}
{'root': 73, 'left': 25}
{'root': 25}
{'root': 25, 'right': 30}
{'root': 30}
{'root': 30, 'left': 27}
{'root': 27}
{'root': 30, 'left': 27, 'right': 35}
{'root': 35}
{'root': 10, 'left': 5, 'right': 20}

Process finished with exit code 0

CodePudding user response：

The left and right keys in your dict should not have data as values, but dictionaries. So assign the result of the recursive call to these keys.

I would also give a default value to the last argument, so the main caller does not have to specify it.

    def traverse(self, current_node=None):
        if not current_node:
            current_node = self.root
        tree = {'data': current_node.data}
        if current_node.left:
            tree.update({'left': self.traverse(current_node.left)})
        if current_node.right:
            tree.update({'right': self.traverse(current_node.right)})
        return tree