Suggest an edit

Improve this article

Refine the answer for “What does a tree consist of?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

A tree (data structure) consists of nodes (vertices) connected by edges. It has a root (a node with no parent), parents and children, siblings, leaves (nodes with no children), and subtrees. The concepts of level/depth, height, and node degree also matter. Every node (except the root) has exactly one parent, and there are no cycles.

## Detailed answer

### Basic elements of a tree

- Node (vertex): stores a value/data and references to child nodes.
- Edges (links): connect nodes; directed from parent to child.
- Root: the single node with no parent.
- Parent and child: the relationship between a node and its immediate descendant.
- Siblings: children of the same parent.
- Leaf: a node with no children. Internal node: a node with at least one child.
- Subtree: a tree rooted at some node together with all of its descendants.
- Path: a sequence of nodes connected by edges. Path length is the number of edges.
- Level/depth: the distance (in edges) from the root to a node. The root's level = 0.
- Height of a node/tree: the maximum path length from a node to a leaf; a tree's height is the height of its root.
- Degree of a node: the number of its children (the branching factor). Tree size: the number of nodes.

### Types of trees (common in interviews)

- General (n-ary) tree: a node can have an arbitrary number of children.
- Binary tree: each node has at most two children (left/right).
- BST (binary search tree): left < node < right by key, operations average O(log n).
- Balanced trees: AVL, red-black, maintain O(log n) height.
- Heaps: min-/max-, support extracting the extremum in O(log n), represented as an array.
- Prefix tree (trie): stores strings by characters, efficient for autocomplete/prefix search.
- B-/B+-trees: optimized for disk storage; the basis of database indexes.

### Representation in memory

- Nodes with a list of children: each node stores an array/list of references to descendants (suits n-ary trees).
- Via an array (for complete binary trees/heaps): for index i → children at 2i+1 and 2i+2, parent at ⌊(i-1)/2⌋.
- Adjacency lists/tables: when a tree is stored as a special case of a graph.

### Tree traversals

1. DFS (depth-first):
  - Preorder (NLR): the node first, then left/children, then right.
  - Inorder (LNR): for a BST, gives a sorted order.
  - Postorder (LRN): children first, then the node (convenient for deletion/counting).
2. BFS (breadth-first, by levels): visiting nodes level by level, top to bottom.

### Code examples

N-ary tree: building it, and a DFS (preorder) and BFS traversal.

```
class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

// Let's build a tree:
//        A
//      /   \
//     B     C
//    / \     \
//   D   E     F
const root = new TreeNode("A");
const b = new TreeNode("B");
const c = new TreeNode("C");
root.children.push(b, c);
b.children.push(new TreeNode("D"), new TreeNode("E"));
c.children.push(new TreeNode("F"));

function dfsPre(node, visit = console.log) {
  if (!node) return;
  visit(node.value);
  for (const child of node.children) dfsPre(child, visit);
}

function bfs(root, visit = console.log) {
  if (!root) return;
  const q = [root];
  while (q.length) {
    const n = q.shift();
    visit(n.value);
    for (const child of n.children) q.push(child);
  }
}

dfsPre(root); // A B D E C F
bfs(root);    // A B C D E F
```

Binary search tree: insertion and an inorder traversal, which yields a sorted output.

```
class BNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function insertBST(node, val) {
  if (!node) return new BNode(val);
  if (val < node.val) node.left = insertBST(node.left, val);
  else node.right = insertBST(node.right, val);
  return node;
}

function inorder(node, visit = console.log) {
  if (!node) return;
  inorder(node.left, visit);
  visit(node.val);
  inorder(node.right, visit);
}

let tree = null;
[7, 3, 9, 1, 5, 8, 10].forEach(v => (tree = insertBST(tree, v)));

inorder(tree); // 1 3 5 7 8 9 10
```

### Applications in web development

- DOM: the document's node tree; rendering and events propagate through the tree (capturing/bubbling).
- AST: the abstract syntax tree in compilers/bundlers (Babel, TypeScript), with transformations over the tree.
- Virtual DOM/component trees (React, Vue): diffing and reconciliation over the tree.
- Routing and search: prefix trees, tries for routes and autocomplete.
- Database indexes (B-/B+-trees), file systems: speed up access to data.

### Key properties and complexities

- Search/insert/delete in a tree usually depend on the height h: O(h). O(log n) for balanced trees, O(n) for degenerate ones (a chain).
- A tree traversal visits every node once: O(n) in time, O(h) in stack/queue memory.
- The choice of representation (pointers/array) affects constants, but not the asymptotics.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts778 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.