What is the difference between using a class and a dictionary to represent a binary tree in Python?

Question

This class represents a node in a tree. I copied its instances to create a tree that looks like this:

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

# Chaining the nodes to represent a tree
root = Node(1)
child1 = Node(2, Node(4), Node(5))
child2 = Node(3)
root.left = child1
root.right = child2

It can also be represented as a graph using a dictionary:

tree = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}

I assume that the first element in the list is the left node, and the second element is the right node.

However, all the blogs and books I came across use a class for a tree and a dictionary for a graph. I was just curious to know the reason for the same.

Answer 1

What is the difference between using a class and a dictionary to represent a binary tree in Python?

There really isn’t much difference in terms of semantics. The main difference is the usability of each method.

, , . .

? . , :

     1
    / \
   2   3
  /   / \
 5   7   9

. , node . :

tree[1][1]

, :

tree.right

, , node, node, . , 9. , :

tree[tree[1][1]][1]

, :

tree.right.right

, ? , , , .

, , . node. , , - , :

# insertion

def insert(key, root, tree):
    if root is None:
        return Node(key)
    elif key < root:
        tree[root][0] = insert(key, tree[root][0], tree)
    else:
        tree[root][1] = insert(key, tree[root][1], tree)
    return root

# deletion

def min_value(node, tree):
    current = node
    while tree[current][0] is not None:
        current = tree[current][0]
    return current


def delete(root, key, tree):
    if root is None:
        return root
    if key < root:
        tree[root][0] = delete(tree[root][0], key, tree)
    elif key < root:
        tree[root][1] = delete(tree[root][1], key, tree)
    else:
        if tree[root][0] is None:
            temp = tree[root][1]
            return temp
        elif tree[root][1] is None:
            temp = tree[root][0]
            return temp
        temp = min_value(tree[root][1], tree)
        tree[root] = tree[temp]
        tree[temp] = tree.pop(root)
        tree[root][1] = delete(tree[root][1], temp)
    return root

, , left, right key.

, , ? , , . ? , .

Answer 2

, root node ( ). , node , : BST, , , Trie ..

, node , , , . .