Tree Data Structure Data Structure
A Tree is a connected acyclic hierarchical graph of N nodes and N - 1 edges with a single root, unique parent-child paths, and recursive subtree structure.
| Operation | Complexity |
|---|---|
| Access | O(n) |
| Search | O(n) |
| Insertion | O(1) with parent ptr |
| Deletion | O(n) |
| Space | O(n) |
Interactive Visualizer · C++ / Python / Java / JS Code
Tree Data Structure
A Tree is a connected, acyclic graph with $N$ nodes and exactly $N - 1$ edges. When rooted at a chosen node root, every other node has a unique parent and zero or more children, creating a recursive hierarchy where every node is the root of its own subtree. Trees power file systems, compilers (ASTs), the HTML DOM, database indexes, and Tree DP.
At a Glance
| Property | Value |
| :--- | :--- |
| Edges in an $N$-node Tree | Exactly $N - 1$ |
| Simple Paths Between Any $(u, v)$ | Exactly 1 unique path |
| Height (Balanced vs. Skewed) | $O(\log N)$ vs. $O(N)$ |
| Traversal (DFS / BFS) | $O(N)$ time, $O(N)$ space |
---
Core Representations & Traversals
- Adjacency List (
vector<vector<int>> adj): Best for unrooted/general trees in algorithms (pass(u, parent)during DFS to avoid cycles). - Parent Array (
parent[i]): Compact $O(N)$ representation (used in Union-Find and rooted trees). - *Children List (
struct Node { int val; vector<Node> children; }):** Classic OOP representation for $N$-ary trees (DOM, directories).
---
Practice Problems
Easy
1. Maximum Depth of an $N$-ary Tree (LeetCode 559)
Find the maximum number of nodes along any root-to-leaf path in an $N$-ary tree.
Approach: Recursive post-order DFS: depth(u) = 1 + max(depth(child)) (or 0 for null). Time: $O(N)$. Space: $O(H)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int maxDepth(int u, int p, const std::vector<std::vector<int>>& adj) {
int best = 0;
for (int v : adj[u]) {
if (v != p) best = std::max(best, maxDepth(v, u, adj));
}
return 1 + best;
}
int main() {
std::vector<std::vector<int>> adj(6);
auto add = [&](int u, int v) { adj[u].push_back(v); adj[v].push_back(u); };
add(0, 1); add(0, 2); add(0, 3); add(1, 4); add(4, 5);
std::cout << maxDepth(0, -1, adj) << "\n"; // 4 (0-1-4-5)
return 0;
}
</details>
2. Level-Order Traversal of an $N$-ary Tree (LeetCode 429)
Group all node values by their depth level using BFS.
Approach: Standard level-by-level BFS using queue size snapshots. Time: $O(N)$. Space: $O(N)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <queue>
#include <vector>
std::vector<std::vector<int>> levelOrder(int root, const std::vector<std::vector<int>>& children) {
std::vector<std::vector<int>> levels;
std::queue<int> q;
q.push(root);
while (!q.empty()) {
int sz = static_cast<int>(q.size());
std::vector<int> cur;
while (sz--) {
int u = q.front(); q.pop();
cur.push_back(u);
for (int v : children[u]) q.push(v);
}
levels.push_back(std::move(cur));
}
return levels;
}
int main() {
std::vector<std::vector<int>> ch = {{1, 2, 3}, {4, 5}, {}, {6}, {}, {}, {}};
auto lvls = levelOrder(0, ch);
std::cout << "Levels: " << lvls.size() << "\n"; // 3
return 0;
}
</details>
---
Intermediate
3. Check If an Undirected Graph Is a Valid Tree (LeetCode 261)
Given $n$ vertices and an edge list, verify whether the graph forms a valid tree.
Approach: An undirected graph is a tree iff it has exactly $n - 1$ edges AND is connected (all $n$ nodes reachable from 0). Time: $O(n)$. Space: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
#include <vector>
bool isValidTree(int n, const std::vector<std::pair<int, int>>& edges) {
if (static_cast<int>(edges.size()) != n - 1) return false;
std::vector<std::vector<int>> adj(n);
for (const auto& [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
std::vector<bool> vis(n, false);
int seen = 0;
auto dfs = [&](auto& self, int u) -> void {
vis[u] = true; ++seen;
for (int v : adj[u]) if (!vis[v]) self(self, v);
};
dfs(dfs, 0);
return seen == n;
}
int main() {
std::cout << std::boolalpha << isValidTree(4, {{0, 1}, {1, 2}, {2, 3}}) << " "
<< isValidTree(4, {{0, 1}, {1, 2}, {2, 0}}) << "\n"; // true false
return 0;
}
</details>
4. Find the Center(s) of an Unrooted Tree (Minimum Height Trees, LeetCode 310)
Find the 1 or 2 root vertices that minimize the tree's height.
Approach: Iteratively peel all leaf nodes (degree == 1) layer by layer via BFS until $\le 2$ nodes remain—the remaining node(s) are the exact tree centers! Time: $O(N)$. Space: $O(N)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
std::vector<int> findTreeCenters(int n, const std::vector<std::pair<int, int>>& edges) {
if (n <= 2) {
std::vector<int> res;
for (int i = 0; i < n; ++i) res.push_back(i);
return res;
}
std::vector<std::vector<int>> adj(n);
std::vector<int> deg(n, 0);
for (const auto& [u, v] : edges) {
adj[u].push_back(v); adj[v].push_back(u);
++deg[u]; ++deg[v];
}
std::queue<int> leaves;
for (int i = 0; i < n; ++i) if (deg[i] == 1) leaves.push(i);
int rem = n;
while (rem > 2) {
int sz = static_cast<int>(leaves.size());
rem -= sz;
while (sz--) {
int u = leaves.front(); leaves.pop();
for (int v : adj[u]) if (--deg[v] == 1) leaves.push(v);
}
}
std::vector<int> centers;
while (!leaves.empty()) { centers.push_back(leaves.front()); leaves.pop(); }
return centers;
}
int main() {
for (int c : findTreeCenters(6, {{0, 3}, {1, 3}, {2, 3}, {4, 3}, {5, 4}})) std::cout << c << " ";
std::cout << "\n"; // 3 4
return 0;
}
</details>
---
Hard
5. $k$-th Ancestor & LCA via Binary Lifting ($O(\log N)$ Query)
Preprocess a rooted tree in $O(N \log N)$ so you can find the $k$-th ancestor and LCA of any pair (u, v) in $O(\log N)$ time.
Approach: Store up[j][u] = the $2^j$-th ancestor of u, computed via up[j][u] = up[j - 1][up[j - 1][u]]. Jump u upward by the set bits of k!
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
#include <vector>
struct BinaryLifting {
int n, LOG;
std::vector<std::vector<int>> up;
std::vector<int> depth;
BinaryLifting(int n, const std::vector<std::vector<int>>& adj, int root = 0)
: n(n), LOG(18), up(LOG, std::vector<int>(n, root)), depth(n, 0) {
auto dfs = [&](auto& self, int u, int p) -> void {
up[0][u] = (p == -1 ? u : p);
for (int j = 1; j < LOG; ++j) up[j][u] = up[j - 1][up[j - 1][u]];
for (int v : adj[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
self(self, v, u);
}
};
dfs(dfs, root, -1);
}
int kthAncestor(int u, int k) const {
for (int j = 0; j < LOG; ++j) if (k & (1 << j)) u = up[j][u];
return u;
}
int lca(int u, int v) const {
if (depth[u] < depth[v]) std::swap(u, v);
u = kthAncestor(u, depth[u] - depth[v]);
if (u == v) return u;
for (int j = LOG - 1; j >= 0; --j) {
if (up[j][u] != up[j][v]) { u = up[j][u]; v = up[j][v]; }
}
return up[0][u];
}
};
int main() {
std::vector<std::vector<int>> adj(6);
auto add = [&](int u, int v) { adj[u].push_back(v); adj[v].push_back(u); };
add(0, 1); add(0, 2); add(1, 3); add(1, 4); add(4, 5);
BinaryLifting bl(6, adj, 0);
std::cout << bl.kthAncestor(5, 2) << " " << bl.lca(3, 5) << "\n"; // 1 1
return 0;
}
</details>
---
Related Structures & Algorithms
- Binary Tree — tree where each node has at most 2 children.
- DP on Trees & Heavy-Light Decomposition — advanced tree algorithms.