Introduction

As part of my goal to finish 52 computer science problems in 52 weeks, I’m going to start on the second problem.

This problem is more of an algorithms interview question that is concerned with navigating around trees.

Setup

Denote a tree T as a graph where any two vertices are connected by exactly one simple path. Suppose that each vertex v in the tree has a pointer to its parent and also to each of its children. Note that this tree does not necessarily need to be a binary tree, or a search tree.

An ancestor of two nodes v₁ and v₂ is a node a such that a can be reached from both v₁ and v₂ by recursively following parent pointers. The lowest common ancestor of v₁ and v₂ is the ancestor a such the distance d(a, v₁) + d(a, v₂) is minimized, where the distance is defined as the number of edges traversed to get between two vertices.

Problem 2

The problem is now as follows: you are given two vertices v₁ and v₂ which you know reside in a tree T which has an infinite number of nodes in it. Find the lowest common ancestor of v₁ and v₂.