Module tree

This module contains tree representations and related algorithms.

Modules

center

This algorithm finds the center(s) of an undirected tree represented by an adjacency list.

height

Tree height Example

isomorphism

Determines if two unrooted trees are isomorphic. This algorithm can easily be modified to support checking if two rooted trees are isomorphic.

lca

Implementation of finding the Lowest Common Ancestor (LCA) of a tree. This impl first finds an Euler tour from the root node which visits all the nodes in the tree. The node height values obtained from the Euler tour can then be used in combination with a sparse table to find the LCA in O(1).

rooting

Often when working with trees we are given them as a graph with undirected edges, however sometimes a better representation is a rooted tree. This module (and the with_parent submodule) contains implementations to build a tree from its adjacency list representation with a given root id.

sum

Tree Sum Example

with_parent

Structs

BinaryTreeNode

Node

Representation of a tree node, which has an id and a Vec of children. children is empty if the node does not have children.