Basic Concepts of Trees

A tree is a data structure composed of nodes or vertices and edges (possibly nonlinear) that does not contain any cycles. A tree without nodes is called an empty (null or empty) tree. A non-empty tree includes a root node and (likely) multiple additional nodes, all nodes forming a multi-level hierarchical structure.

A tree is a special type of graph (graphs will be mentioned in subsequent articles).

Prefix Tree (Trie)

Directed Tree

Its edges have direction. A tree is a connected graph without simple circuits.

The number of edges starting from node v is called the outdegree of v. The number of edges ending at v is called the indegree of v. In the figure above, node v2 has an indegree of 1 and an outdegree of 2.

Circuits and Connectivity

Height and Nodes

Binary Tree

Binary trees are further divided into: perfect binary tree, complete binary tree, full binary tree

Perfect Binary Tree (Full Binary Tree)

Every node except leaf nodes has two child nodes, and every level (including the last level) is completely filled.

Complete Binary Tree

A complete binary tree satisfies a perfect binary tree from the root node to the second-to-last level. The last level can be incompletely filled, with all leaf nodes aligned to the left.

Full Binary Tree

All non-leaf nodes have a degree of 2. In other words: If you have children, you must have exactly two children.

Article Link: