A tree is a non-linear structure for hierarchical data: a file system, the DOM of an HTML document, an org chart, an expression tree. A tree generalizes a linked list: a node has several children instead of one next. There are no cycles, and every node (except the root) has exactly one parent.
Terms
| Term | Meaning |
|---|---|
| Root | the only node without a parent |
| Leaf | a node without children |
| Parent / child / sibling | directly above / below / other children of the same parent |
| Ancestor / descendant | nodes above / below along the path |
| Depth | the number of edges from the root to the node (the root has 0) |
| Height | the number of edges from the node to the deepest leaf (a leaf has 0) |
| Level | the nodes of the same depth |
| Subtree | a node and all its descendants |
| Degree | the number of children of a node |
The height of a tree is the height of its root. A tree with n nodes has n - 1 edges.
The node class
class TreeNode:
def __init__(self, value, children=None):
self.value = value
self.children = children or []
def sample():
return TreeNode("A", [
TreeNode("B", [TreeNode("E"), TreeNode("F")]),
TreeNode("C"),
TreeNode("D", [TreeNode("G")]),
])
def height(node):
return 1 + max((height(c) for c in node.children), default=-1)