EttTree - Euler Tour Tree with Treap

A C# implementation of a dynamic tree data structure using Euler Tour Trees backed by a Treap (randomized binary search tree). This structure enables efficient tree operations while maintaining the ability to quickly compare nodes by their DFS order.

Features

• O(1) DFS index comparison between any two nodes in the same tree
• O(1) parent lookup (stored reference)
• O(log n) insertion and removal of subtrees
• O(log n) navigation to siblings, first/last child
• O(k) non-recursive iteration over children or entire subtrees
• No global tree manager - trees are self-contained; subtrees become independent trees when removed
• Generic - TreeNode<T> supports any payload type

Rationale

The Problem

Traditional tree representations (parent/child pointers) make certain operations expensive:

Operation	Traditional Tree	EttTree
"Is A before B in DFS?"	O(n)	O(log n)
Move subtree to new parent	O(1) pointer swap	O(log n)
Non-recursive DFS iteration	Requires stack	O(1) per node
Get DFS index of node	O(n)	O(log n)
Get parent	O(1)	O(1)

The Solution: Euler Tour + Treap

An Euler Tour linearizes a tree into a sequence by recording each node twice: once when entering (DFS down) and once when exiting (DFS up).

Tree:           Euler Tour Sequence:
    A           [A_enter, B_enter, B_exit, C_enter, D_enter, D_exit, C_exit, A_exit]
   / \
  B   C
      |
      D

This sequence is stored in a Treap - a randomized BST that maintains balance through random priorities. The Treap uses implicit keys (subtree sizes) rather than explicit keys, treating the Euler Tour as an ordered sequence.

Key insight: A node's position in the Euler Tour directly corresponds to its DFS order. Comparing two nodes' positions tells you their relative DFS order in O(log n) time.

Data Structure

TreeNode<T>

The main API for working with trees:

public class TreeNode<T>
{
    public T Value { get; set; }
    
    // Navigation
    public TreeNode<T>? Parent { get; }          // O(1) - stored reference
    public TreeNode<T>? FirstChild { get; }      // O(log n)
    public TreeNode<T>? LastChild { get; }       // O(log n)
    public TreeNode<T>? NextSibling { get; }     // O(log n)
    public TreeNode<T>? PreviousSibling { get; } // O(log n)
    
    // DFS index (O(log n))
    public int GetDFSIndex();
    
    // Tree manipulation (all O(log n))
    public void Remove();
    public void InsertFirstChild(TreeNode<T> newNode);
    public void InsertLastChild(TreeNode<T> newNode);
    public void InsertSiblingBefore(TreeNode<T> newNode);
    public void InsertSiblingAfter(TreeNode<T> newNode);
    public void RemoveAllChildren();
    
    // Iteration (O(1) per element)
    public ChildrenEnumerable Children { get; }
    public SubtreeEnumerable Subtree { get; }
}

EttNode (Internal)

Each TreeNode<T> contains two EttNode instances:

• EttEnter - marks the start of this node's range in the Euler Tour
• EttExit - marks the end of this node's range

The Euler Tour sequence for a subtree is: [Enter, ...descendants..., Exit]

public class EttNode
{
    public int Priority { get; }      // Random priority for Treap balancing
    public int Size { get; }          // Subtree size for implicit indexing
    public EttNode? Left, Right, Parent;
    public TreeNode<T> Owner { get; }
    
    // Instance methods
    public EttNode GetRoot();              // O(log n) - walk up to root
    public int GetIndex();                 // O(log n) - calculate position
    public EttNode? GetNext();             // O(log n) - next in sequence
    public EttNode? GetPrevious();         // O(log n) - previous in sequence
    public int GetHeight();                // O(n) - for testing
    public EttNode? GetNodeAtIndex(int index);  // O(log n)
    
    // Static Treap operations
    public static EttNode? Merge(EttNode? l, EttNode? r);
    public static (EttNode? L, EttNode? R) Split(EttNode? root, int k);
}

Usage Examples

Creating a Tree

var root = new TreeNode<string>("Root");
var child1 = new TreeNode<string>("Child1");
var child2 = new TreeNode<string>("Child2");
var grandchild = new TreeNode<string>("Grandchild");

root.InsertLastChild(child1);
root.InsertLastChild(child2);
child1.InsertFirstChild(grandchild);

Comparing DFS Order

// O(log n) comparison - no traversal needed!
if (nodeA.GetDFSIndex() < nodeB.GetDFSIndex())
{
    Console.WriteLine("A comes before B in DFS order");
}

Iterating Over Children

// Non-recursive, allocation-free iteration
foreach (var child in parent.Children)
{
    Console.WriteLine(child.Value);
}

Iterating Over Entire Subtree (DFS Order)

// Non-recursive DFS traversal
foreach (var node in root.Subtree)
{
    Console.WriteLine(node.Value);
}

Moving Subtrees

// Remove from current location and insert elsewhere - O(log n)
child1.Remove();  // child1 is now an independent tree
newParent.InsertFirstChild(child1);  // child1 is now under newParent

Navigation

var parent = node.Parent;           // O(1) - stored reference
var firstChild = node.FirstChild;   // O(log n)
var next = node.NextSibling;        // O(log n)

// Check if node is a leaf
if (node.FirstChild == null)
{
    Console.WriteLine("This is a leaf node");
}

Complexity Analysis

Operation	Time Complexity	Notes
Parent	O(1)	Stored reference
GetDFSIndex()	O(log n)	Walk up to root, summing sizes
FirstChild, LastChild	O(log n)	GetNext()/GetPrevious() + parent check
NextSibling, PreviousSibling	O(log n)	GetNext()/GetPrevious() + parent check
InsertFirstChild, InsertLastChild	O(log n)	Split + Merge
InsertSiblingBefore, InsertSiblingAfter	O(log n)	Split + Merge
Remove	O(log n)	Split + Split + Merge
RemoveAllChildren	O(k log n)	k = number of direct children
Iterate Children	O(k log n)	k = number of children
Iterate Subtree	O(m log n)	m = subtree size

Space Complexity: O(n) where n is the number of nodes. Each TreeNode creates 2 EttNode instances.

Implementation Details

Treap Balancing

Each EttNode is assigned a random priority at creation. The Treap maintains the heap property on priorities while preserving sequence order through implicit keys. This ensures O(log n) expected height regardless of insertion order.

Parent Pointers

The TreeNode<T>.Parent property is a stored reference that is maintained by all tree manipulation methods:

• Remove() sets _parent = null
• InsertFirstChild() / InsertLastChild() sets _parent = this
• InsertSiblingBefore() / InsertSiblingAfter() sets _parent = this._parent

This provides O(1) parent access while keeping the tree structure consistent.

Treap Navigation

The EttNode class provides GetNext() and GetPrevious() methods for efficient O(log n) navigation through the Euler Tour sequence:

• If there's a right/left subtree, go to its leftmost/rightmost node
• Otherwise, walk up until finding an ancestor where we came from the left/right

These methods are used by FirstChild, LastChild, NextSibling, and PreviousSibling combined with the stored parent reference for O(log n) navigation.

Split and Merge

The fundamental Treap operations:

• Split(root, k): Divides the sequence at index k into two Treaps
• Merge(left, right): Combines two Treaps, maintaining sequence order

All tree manipulations are compositions of these operations:

InsertFirstChild(parent, new):
    Split at parent.Enter + 1
    Merge(left, new.tree, right)

Remove(node):
    Split at node.Enter
    Split at node.Exit + 1  
    Merge(before, after)  // middle is now independent

No Shared State

When a subtree is removed, it becomes a completely independent tree. There is no global tree registry - the tree structure is defined entirely by the Treap connectivity of its EttNode instances.

Testing

The implementation includes comprehensive tests covering:

• Basic connectivity and DFS ordering
• Subtree extraction and re-parenting
• Sibling insertion and index shifting
• Navigation properties
• Edge cases (lone nodes, root operations, deep trees)
• Stress testing for Treap balance (1000+ nodes)

Run tests with:

dotnet test

License

MIT

References

• Henzinger, M. R., & King, V. (1999). Randomized fully dynamic graph algorithms with polylogarithmic time per operation.
• Tarjan, R. E. (1979). A class of algorithms which require nonlinear time to maintain disjoint sets.