#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/euler-tour-trees

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/link-cut-trees/euler-tour-trees

Repovive

Euler Tour Trees - Link-Cut Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units

Open in Course

Euler Tour Trees

Alternative approach

Euler Tour Trees (ETT) are another dynamic tree structure:

Store Euler tour of tree in a balanced BST
Link/cut by splicing tours
Subtree queries are range queries on tour

Comparison:

	Link-Cut	ETT
Path query	$O(\log n)$	Not native
Subtree query	Complex	$O(\log n)$
Implementation	Hard	Medium

ETT is better for subtree operations.

Link-Cut is better for path operations. Choose based on what queries you need.

HannahHi! I'm Hannah. Let me know if you need help understanding anything!