Trees

Root: node with no incoming edges.
Children: nodes with some incoming edges.
Sibling: nodes having the same parent.
Leaf: nodes with no children.
Height: number of edges between node A and B .

A Tree is a Connected Acyclic Graph. We will study the Graphs later, so don't worry if you do not get it immediately.

A n-ary tree is a Tree in which each node contains at most n children.

The most common one is the Binary Tree, where each node has at most 2 children ( $n = 2$ ).

As for the Linked Lists, there is no Python data type for trees. However, we can easily define a Binary one:

from typing import Generic, Optional, TypeVar

T = TypeVar("T")


class TreeNode(Generic[T]):
    def __init__(
        self,
        val: T,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right

Or a n-ary tree:

from typing import Generic, List, Optional, TypeVar

T = TypeVar("T")


class TreeNode(Generic[T]):
    def __init__(self, val: T, children: Optional[List["TreeNode"]] = None) -> None:
        self.val = val
        self.children = [] if not children else children