DSA Series · Trees · Part 1

Introduction to Trees

March 2026 · 6 min read

What is a Tree?

A tree is a connected, acyclic graph where one distinguished node is called the root. Every other node has exactly one parent, and zero or more children. Trees appear everywhere: file systems, the DOM, compilers (ASTs), databases (B-trees), and network routing.

Figure 1: A binary search tree with 7 nodes. Root = 10.

▶ Build This Tree Step-by-Step

Watch how a binary search tree is constructed by inserting nodes one at a time.

Key Terminology

Root: The topmost node (no parent).
Leaf: A node with no children.
Depth: Distance (edges) from root to node.
Height: Longest path from the node down to a leaf. Height of tree = height of root.
Degree: Number of children a node has.
Subtree: A node and all its descendants.

Figure 2: Tree anatomy, depth levels, root (A), internal nodes (B, C, D), and leaves (E, F, G). Height of tree = 3.

Binary Trees

A binary tree is a tree where each node has at most two children, called left and right.

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

Types of Binary Trees

Figure 3: Three categories of binary trees side by side.

▶ Interactive Depth & Height Explorer

Click any node to see its depth (from root) and height (to deepest leaf). The path lights up.

Click a node above ↑

Summary

Trees are connected acyclic graphs with a root node.
Key properties: depth, height, degree, and subtree.
Binary trees restrict each node to at most two children.
Full, complete, and degenerate are the main binary tree categories.