What does a tree consist of?

AlgorithmsJunior~3 min read

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

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).

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.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.