Tree Basics

Introduction

Trees in graph theory look just like trees in real life, except that when solving problems we usually place the root at the top. This data structure looks like an upside-down tree, which is how it got its name.

Definitions

A tree with no fixed root vertex is called an unrooted tree. An unrooted tree has several equivalent formal definitions:

• A connected undirected graph with $n$ vertices and $n-1$ edges.

• A connected undirected acyclic graph.

• An undirected graph with exactly one simple path between every pair of vertices.

• A connected graph in which every edge is a bridge.

• A graph with no cycle such that, after adding an edge between any two distinct vertices, the resulting graph contains exactly one cycle.

Starting with an unrooted tree, designating a vertex as the root produces a rooted tree. A rooted tree is still often represented as an undirected graph; only the parent-child relationships between vertices are specified, as described below.

Tree Terminology

Applicable to Unrooted and Rooted Trees

• Forest: A graph whose every connected component is a tree. By definition, a tree is also a forest.

• Spanning tree: A spanning subgraph of a connected undirected graph that is also a tree. Equivalently, choose $n - 1$ edges from the graph so that all vertices are connected.

• Leaf node of an unrooted tree: A vertex with degree at most $1$.

  ???+ question "Why not degree exactly $1$?" Consider $n = 1$.

• Leaf node of a rooted tree: A vertex with no children.

Applicable Only to Rooted Trees

• Parent: For every vertex other than the root, its parent is defined as the second vertex on the path from that vertex to the root.
  The root has no parent.
• Ancestor: Any vertex other than the vertex itself on the path from a vertex to the root.
  The root has no ancestors.
• Child: If $u$ is the parent of $v$, then $v$ is a child of $u$.
  The order of children is generally irrelevant; a binary tree is an exception.
• Depth of a vertex: The number of edges on the path to the root.
• Height of a tree: The maximum depth among all vertices.
• Sibling: Multiple children of the same parent are siblings.
• Descendant: A child or a descendant of a child.
  Equivalently, if $u$ is an ancestor of $v$, then $v$ is a descendant of $u$.

• Subtree: The subgraph containing a vertex after the edge connecting it to its parent is removed.

  

Special Trees

• Chain/path graph: A tree in which at most $2$ edges are incident to any vertex.

• Star: A tree in which there is a vertex $u$ such that every vertex other than $u$ is adjacent to $u$.

• Rooted binary tree: A rooted tree in which every vertex has at most two children. The order of the two children is often distinguished; they are called the left and right children.
  In most contexts, binary tree means a rooted binary tree.

• Full/proper binary tree: A binary tree in which every vertex has either 0 or 2 children. In other words, every vertex is either a leaf or has both a nonempty left subtree and a nonempty right subtree.

  

• Complete binary tree: Only vertices in the bottom two levels may have degree less than 2, and the vertices in the bottom level occupy a contiguous range starting from the far left.

  

• Perfect binary tree: A binary tree in which all leaves have the same depth and every non-leaf vertex has exactly two children.

  

OIers usually use “full binary tree” to mean a perfect binary tree.

Storage

Recording Only Parents

Use an array parent[N] to record the parent of every vertex.

This representation provides relatively little information and is inconvenient for top-down traversal. It is commonly used in bottom-up recurrence problems.

Adjacency List

• For an unrooted tree: allocate a linear list for every vertex and record all vertices adjacent to it.

  std::vector<int> adj[N];
  

• For a rooted tree:
  • Method 1: If the input is an undirected graph, it can still be stored in the form above. The parent-child relationships will be distinguished below.
  • Method 2: If the input guarantees the parent-child relationships, use that information. Allocate a linear list for every vertex and record all of its children; if necessary, record its parent in another array.

    std::vector<int> children[N];
    int parent[N];
    

    The std::vector can of course be replaced by another representation, such as a linked list.

Left-Child Right-Sibling Representation

Process

There is a simple representation for rooted trees.

First, choose an arbitrary order for the children of every vertex.

Then record two values for every vertex: its first child child[u] and its next sibling sib[u]. If it has no children, child[u] is empty; if it is the last child of its parent, sib[u] is empty.

Implementation

The children of a vertex can be traversed as follows.

int v = child[u];  // Start from the first child
while (v != EMPTY_NODE) {
  // ...
  // Process child v
  // ...
  v = sib[v];  // Move to the next child, which is a sibling of v
}

It can also be written more compactly as follows.

for (int v = child[u]; v != EMPTY_NODE; v = sib[v]) {
  // ...
  // Process child v
  // ...
}

Binary Trees

Record the left and right children of every vertex.

int parent[N];
int lch[N], rch[N];
// -- or --
int child[N][2];

Tree Traversal

DFS on a Tree

DFS on a tree proceeds by visiting the root first, then visiting the subtree of each child of the root in turn.

It can be used to determine the depth, parent, and other information for every vertex.

DFS Traversal of a Binary Tree

Preorder Traversal

Traverse a binary tree in the order root, left, right.

void preorder(BiTree* root) {
  if (root) {
    cout << root->key << " ";
    preorder(root->left);
    preorder(root->right);
  }
}

Inorder Traversal

Traverse a binary tree in the order left, root, right.

void inorder(BiTree* root) {
  if (root) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}

Postorder Traversal

Traverse a binary tree in the order left, right, root.

void postorder(BiTree* root) {
  if (root) {
    postorder(root->left);
    postorder(root->right);
    cout << root->key << " ";
  }
}

Reconstruction

Given the inorder traversal and one other traversal, the third traversal can be determined.

1. The first vertex in preorder is root, and the last vertex in postorder is root.
2. Determine the root first. In the inorder traversal, the vertices to its left form the left subtree, and those to its right form the right subtree.
3. Treat each subtree as a new tree and apply the same rules recursively.

BFS on a Tree

Starting from the root, visit vertices strictly level by level.

During BFS, the depth and parent of every vertex can also be determined along the way.

Level-Order Traversal of a Tree

Level-order traversal visits vertices horizontally, one level at a time, according to their levels from the root to the leaves. From the definition of BFS, its traversal order is a level-order traversal. However, level-order traversal distinguishes different levels, so its result is usually represented as a two-dimensional array.

For example, the level-order traversal of the tree below is [[1], [2, 3, 4], [5, 6]] (from left to right within each level).

vector<vector<int>> levelOrder(Node* root) {
  if (!root) {
    return {};
  }
  vector<vector<int>> res;
  queue<Node*> q;
  q.push(root);
  while (!q.empty()) {
    int currentLevelSize = q.size();  // Number of nodes at the current level
    res.push_back(vector<int>());
    for (int i = 0; i < currentLevelSize; ++i) {
      Node* cur = q.front();
      q.pop();
      res.back().push_back(cur->val);
      for (Node* child : cur->children) {  // Add all children
        q.push(child);
      }
    }
  }
  return res;
}

Morris Traversal of a Binary Tree

The central problem in binary-tree traversal is how to return to the current vertex and continue after traversing one of its subtrees. Both recursive and iterative binary-tree traversals use a stack to record the return path and move from lower levels back to higher ones. Its space complexity is $O(\log n)$ in the best case and $O(n)$ in the worst case (when the binary tree is a chain).

Morris traversal avoids using a stack. It uses the unused right pointer of a low-level vertex to point back to an upper vertex, thereby moving from lower levels back to higher ones.

Morris Traversal Process

Suppose we arrive at the current vertex cur; initially, we are at the root.

1. If cur is empty, stop the traversal; otherwise, continue as follows.
2. If cur has no left subtree, move cur to the right (cur = cur->right).
3. If cur has a left subtree, find the rightmost vertex in that subtree and call it mostRight.
   • If mostRight's right pointer is empty, make it point to cur, then move cur to the left (cur = cur->left).
   • If mostRight's right pointer points to cur, change it to null, then move cur to the right (cur = cur->right).

For example, suppose cur starts by visiting vertex 1.

When cur first visits vertex 2, it finds the rightmost vertex 4 in the left subtree and makes vertex 4's right pointer point to cur (vertex 2).

cur returns to the upper level through vertex 4's right pointer. When it visits vertex 2 for the second time, it finds the rightmost vertex 4 in the left subtree, changes vertex 4's right pointer to null, and then continues to the right subtree. The remaining process is omitted.

The traversal order of the entire tree is 1242513637. Vertices with a left subtree are visited twice, while vertices without a left subtree are visited only once.

void morris(TreeNode* root) {
  TreeNode* cur = root;
  while (cur) {
    if (!cur->left) {
      // If the current node has no left child, output its value and enter the right subtree
      std::cout << cur->val << " ";
      cur = cur->right;
      continue;
    }
    // Find the rightmost node in the current node's left subtree
    TreeNode* mostRight = cur->left;
    while (mostRight->right && mostRight->right != cur) {
      mostRight = mostRight->right;
    }
    if (!mostRight->right) {
      // If the right pointer of the rightmost node is null, point it to the current node and enter the left subtree
      mostRight->right = cur;
      cur = cur->left;
    } else {
      // If the right pointer of the rightmost node points to the current node, the left subtree has been traversed; output the current value and enter the right subtree
      mostRight->right = nullptr;
      std::cout << cur->val << " ";
      cur = cur->right;
    }
  }
}

Unrooted Trees

Process

Tree traversal is generally depth-first; the main thing to watch out for is visiting a vertex more than once.

Because a tree is acyclic, it is enough to record which vertex the current vertex was reached from, and then enter every adjacent vertex other than that one. This avoids repeated visits.

void dfs(int u, int from) {
  // Recursively enter every child other than from
  // For the starting node, from is empty, so every adjacent node is visited, as desired
  for (int v : adj[u])
    if (v != from) {
      dfs(v, u);
    }
}

// At the start of the traversal
int EMPTY_NODE = -1;  // A nonexistent index
int root = 0;         // Choose any vertex as the starting point
dfs(root, EMPTY_NODE);

Rooted Trees

For a rooted tree, the parent-child relationships must be distinguished.

Consider the traversal above. If the traversal starts at the root, then when a vertex is visited, the value of from is the index of its parent.

This method can determine the parent of every vertex and the list of children from an undirected input.

Part of this page is adapted from the blog post Binary tree: preorder, inorder, and postorder traversal, under the CC 4.0 BY-SA license.