Abstract / Summary

Find the node on a tree that is closest to two given nodes.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 53% (300k+ submissions).

Typical patterns to solve this problem:

• Depth First Search
• Graph Theory

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the “closest meeting node” problem on a directed graph represented by an adjacency list edges. Starting from two distinct source vertices node1 and node2, the algorithm walks forward along the unique outgoing edge of each node, looking for the first vertex that can be reached from both sources with the smallest distance. The method returns the identifier of that meeting node or -1 if no such node exists.

Initialization

The method begins by creating two empty sets, have1 and have2. These collections record every vertex visited while traversing from node1 and node2, respectively.

have1 = set()
have2 = set()

The use of hash-based sets enables constant-time checks for prior visitation, which is crucial for detecting intersections and cycles efficiently.

Main Traversal Loop

A single while loop drives the simultaneous walk from both sources. The loop continues as long as at least one of the current pointers is not the sentinel value -1, which denotes the end of a path.

while node1 != -1 or node2 != -1:

Immediate Meeting

The first conditional inside the loop checks whether the two pointers currently reference the same vertex. If they do, the algorithm has found a meeting point and returns it instantly.

if node1 == node2:
    return node1

Cross-Path Intersection

If the pointers differ, the algorithm tests whether the vertex reached from one side has already been visited from the opposite side. This captures the scenario where the two walks intersect after a different number of steps.

if node1 in have2:
    if node2 < node1 and node2 in have1:
        return node2
    return node1
if node2 in have1:
    return node2

The nested condition node2 < node1 and node2 in have1 handles the rare case where both sides have already visited each other’s current vertices, ensuring the smallest index is chosen when distances are equal.

Cycle Detection

When a pointer revisits a vertex that it has already seen on its own path, a cycle is detected. The algorithm then disables further progress on that side by assigning -1 to the pointer, effectively pruning the cyclic portion.

if node1 in have1:
    node1 = -1
if node2 in have2:
    node2 = -1

Advancement

If a pointer is still active (not -1), the current vertex is added to its visitation set, and the pointer moves to the next vertex indicated by the edges array.

if node1 != -1:
    have1.add(node1)
    node1 = edges[node1]
if node2 != -1:
    have2.add(node2)
    node2 = edges[node2]

Termination

When both pointers become -1, meaning neither walk can proceed further and no meeting node has been found, the method returns -1 to signal failure.

return -1

Edge Cases Handled

The algorithm gracefully manages several special situations:

• Identical Starting Nodes - If node1 and node2 are the same at the outset, the immediate meeting check returns that node without any traversal.
• One-Sided Termination - When one walk reaches a dead end (-1) while the other continues, the loop still processes the active side, allowing a possible later intersection.
• Self-Loops and Cycles - By detecting revisits within the same traversal (node in have), the code prevents infinite looping and stops exploring a cyclic path once it is recognized.
• Simultaneous Intersection - The nested condition that compares indices (node2 < node1) ensures that when both sides have already visited each other’s current nodes, the algorithm selects the node with the smaller identifier, adhering to the problem’s tie-breaking rule.
• Disconnected Graph Segments - If the two source vertices belong to entirely separate components, the loop exhausts both walks and ultimately returns -1.

Performance Optimizations

The implementation incorporates several techniques that keep execution efficient:

• Single Pass Traversal - By advancing both pointers inside the same loop, the algorithm avoids separate scans of the graph, reducing overall work.
• Hash-Set Membership Checks - Using set objects for have1 and have2 provides O(1) average-case lookups for previously visited vertices, which is essential for rapid detection of intersections and cycles.
• Early Exit Conditions - The immediate return when the two pointers coincide or when a cross-path intersection is found prevents unnecessary continuation once the answer is known.
• Cycle Pruning - As soon as a cycle is detected on either side, the corresponding pointer is set to -1. This eliminates repeated traversal of the same cycle and limits the number of iterations to the length of the acyclic prefix of each path.

Overall, the method leverages set-based bookkeeping and a tightly controlled loop to achieve a solution that scales well with the size of the input graph while handling a broad range of edge conditions.

Imagine two friends starting at two different houses in a big maze. Each house has a special sign that points to the next house you must visit. The friends start walking at the same time, moving from house to house following those signs.

The two lists keep track of all the houses each friend has already walked through so that they do not get lost. As they walk, they always check if they are currently standing in the same house. If they land on the same spot, they have found the place where they can meet.

Sometimes a friend might walk into a house that the other friend already visited. When that happens, the friends look at who has been where to figure out the best spot to gather. If a house points back to one they have already visited, they stop walking in that direction so they do not go in circles. They keep moving forward, one step at a time, until they either find a place to be together or realize that there is no path that connects them at the same house.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java	Python		C++					TS
	WalkCCC	Java	Python		C++
	leetcode.ca	Java	Python		C++	C#	Go	Rust	Swift	TS
	Progiez	Java	Python		C++
github	charles-wangkai	Java
	everthis			JS
	fsq				C++
	JoshCrozier			JS
	lkwq007		Python
	trung-hn		Python
	varunu28	Java
	vthwang	Java
	wisdompeak				C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, Swift, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality