Python Forum

Bellow I have some code, I was wondering how it is possible that the object root looks like if I have list of object (I expect a single object)

I get the values after inorder function:
4
6
8
32
58
59
98

But I expect to get get only 4
since root = insert(root, 4)is overriding the object or am I missing something.
(My goal is to understand how this list of objects is created)

class Node:
    def __init__(self, key):
        self.key=key
        self.left= None
        self.right=None
        
def inorder(root):
    if root is not None:
        inorder(root.left)
        print(root.key)
        inorder(root.right)
        
def insert(node, key):
    if node is None:
        return Node(key)
    
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right,key)
    
    return node

def minValueNode(node):
    current = node
    
    while(current.left is not None):
        current = current.left
        
    return current


def deleteNode(root, key):
    
    if root is None:
        return root
    
    if key < root.key:
        root.left = deleteNode(root.left, key)
    elif(key>root.key):
        root.right= deleteNode(root.right, key)
        
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp
        
        elif root.right is None:
            temp = root.left
            root = None
            return temp
        
        temp = minValueNode(root.right)
        root.key = temp.key
        root.right = deleteNode(root.right, temp.key)
        
    return root
    
root = None
root = insert(root, 58)

root = insert(root, 32)
root = insert(root, 8)
root = insert(root, 59)
root = insert(root, 98)
root = insert(root, 6)
root = insert(root, 4)
inorder(root)

This is a standard binary tree. Basically, it's a linked list combined with a sorting algorithm.

When inserting a value, insert() determines the current state of the node and evaluates how the new value compares. If the value is None, it creates a node. If the new value is lower, it recurses and evaluates the left child node of the current node and repeats the process. Likewise, if the value is higher, it does the same process to the right child node.

The end result is a data structure of nodes that know about other nodes, their children. Plus, they're all sorted by value. When you use inorder() on this data structure, it asks a question: Who are your children and where do they live? Then, it asks the left child the same question until there are no more children. It prints the value of the last child, then that child's parent, and then it asks the same question to the right child.

Geeks for Geeks has a great series on binary trees and different variants. They have gifs to demonstrate them too.