Learn what trees are, the vocabulary used to describe them, and how they differ from linked lists.

Trees

A tree is a hierarchical data structure made of nodes connected by edges, where each node can have multiple children but only one parent. Unlike arrays and linked lists, which are linear, a tree branches.

Think of a tree like an actual family tree, or the folder structure on your computer. A folder can contain multiple subfolders, each subfolder can contain more subfolders, and so on — but every folder (except the root) has exactly one parent folder.

Tree anatomystructure

root

internal node

leaf

rootA — no parent

leavesD, E, F — no children

B's childrenD and E

height2 (A → B → D)

Vocabulary

Term	Meaning
Root	The top node — has no parent
Node	Any element in the tree
Edge	The connection between a parent and a child
Parent	A node with one or more children
Child	A node directly connected below a parent
Leaf	A node with no children
Subtree	A node and all of its descendants
Depth	Number of edges from the root to a node
Height	Number of edges on the longest path from a node to a leaf
Level	All nodes at the same depth

            A          ← root, depth 0
          /   \
         B     C        ← depth 1
        / \     \
       D   E     F      ← depth 2, D/E/F are leaves

Here, A is the root. D, E, F are leaves. B is the parent of D and E. The height of the tree is 2.

Trees vs linked lists

A linked list is actually a special case of a tree — one where every node has at most one child. Trees generalize this to allow multiple children.

	Linked List	Tree
Children per node	1	0 or more
Structure	Linear	Hierarchical
Traversal	One direction	Multiple paths possible
Use case	Sequences	Hierarchies, search, priority

A tree node in Python

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []   # general tree — any number of children


# binary tree — special case, exactly 2 children max
class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

A binary tree restricts every node to at most 2 children — conventionally called left and right. It is by far the most common tree type in computer science and the focus of the rest of this section.

Why trees matter

Hierarchical data — file systems, organization charts, HTML/DOM structure, JSON nesting.

Fast search — a balanced binary search tree finds any value in O(log n), much faster than a linked list's O(n).

Priority systems — heaps (a special tree) always give instant access to the minimum or maximum element.

Decision making — decision trees in machine learning, game trees in chess engines.

Autocomplete — tries (a tree variant) power search-as-you-type features.

Types of trees covered in this section

Binary tree — each node has at most 2 children. The foundation for everything else.

Binary search tree (BST) — a binary tree with an ordering rule: left child is always smaller, right child is always larger. Enables O(log n) search.

Heap — a binary tree where every parent is smaller (min-heap) or larger (max-heap) than its children. Powers priority queues.

Traversal — the different orders for visiting every node: preorder, inorder, postorder, and level-order (BFS).

Most tree problems in interviews are about binary trees specifically — not general trees. Master the binary tree pattern first; it transfers directly to BSTs and heaps, which are just binary trees with extra rules.

What is coming in this section

Binary tree — structure, insertion, and basic operations.

Binary search tree — the ordering property, search, insert, and delete.

Tree traversal — all four traversal orders, visualized step by step.

Heap — min-heap and max-heap, used to build priority queues.

Trees — Introduction