Tree Data Structure

What is a Tree?

A tree is a hierarchical data structure consisting of nodes, with a single node as the root and zero or more child nodes. Each node contains a value and references to its child nodes. Trees are used to represent hierarchical relationships and are the basis for many data structures, including binary trees, AVL trees, and heaps.

Common Operations

Insertion

function insert(root, value):
    if root is null:
        return new Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

Traversal (In-Order)

function inorderTraversal(root):
    if root is not null:
        inorderTraversal(root.left)
        print(root.value)
        inorderTraversal(root.right)

Deletion

function deleteNode(root, key):
    if root is null:
        return root
    if key < root.value:
        root.left = deleteNode(root.left, key)
    elif key > root.value:
        root.right = deleteNode(root.right, key)
    else:
        if root.left is null:
            return root.right
        elif root.right is null:
            return root.left
        minValue = findMin(root.right)
        root.value = minValue
        root.right = deleteNode(root.right, minValue)
    return root