Tree<T> Class

Definition

Namespace

Bodu.Collections.Generic.Trees

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

Tree{T}.Traversal.cs

Represents a node in a mutable n-ary tree. Each instance is simultaneously a node carrying a value and the root of the subtree formed by its descendants.

public sealed class Tree<T>

Type Parameters

T

The type of the value stored at each node.

Inheritance

object

Tree<T>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

ComparableExtensions.AtLeast<T>(T, T, IComparer<T>)

ComparableExtensions.AtMost<T>(T, T, IComparer<T>)

ComparableExtensions.IsEqualTo<T>(T, T, IComparer<T>)

ComparableExtensions.Max<T>(T, T, IComparer<T>)

ComparableExtensions.Min<T>(T, T, IComparer<T>)

Remarks

A Tree<T> exposes its Parent and ordered Children and supports structural mutation through AddChild(T), AddChild(Tree<T>), RemoveChild(Tree<T>), and Remove(). Traversals (PreOrder(), PostOrder(), LevelOrder()) are evaluated iteratively, so arbitrarily deep trees can be walked without risking a stack overflow.

The tree is not thread-safe for concurrent mutation. Mutating the tree while a traversal is being enumerated produces undefined results.

Constructors

Tree(T)

Initializes a new instance of the Tree<T> class as a root node with the specified value.

public Tree(T value)

Parameters

value T

The value stored at the node.

Tree(T, IEnumerable<T>)

Initializes a new instance of the Tree<T> class as a root node with the specified value and a child created for each supplied child value.

public Tree(T value, IEnumerable<T> childValues)

Parameters

value T

The value stored at the node.

childValues IEnumerable<T>

The values from which to create child nodes.

Exceptions

ArgumentNullException

childValues is null.

Properties

ChildCount

Gets the number of immediate children.

public int ChildCount { get; }

Property Value

int

The child count.

Children

Gets the ordered list of child nodes.

public IReadOnlyList<Tree<T>> Children { get; }

Property Value

IReadOnlyList<Tree<T>>

A read-only view of the node's children.

Remarks

The returned collection is a live, read-only view over the node's children: it reflects subsequent AddChild(T) and RemoveChild(Tree<T>) operations but cannot be mutated directly, preserving the parent and acyclicity invariants the mutating members enforce.

Depth

Gets the depth of this node, measured as the number of edges from the root.

public int Depth { get; }

Property Value

int

Zero for a root node, increasing by one per level.

Remarks

This property is computed on each access by walking the parent chain to the root; it is O(d) in the depth of this node rather than a constant-time field read. Cache the result when reading it repeatedly in a hot path.

Height

Gets the height of the subtree rooted at this node, measured as the number of edges on the longest path to a descendant leaf.

public int Height { get; }

Property Value

int

Zero for a leaf node.

Remarks

This property is computed on each access by traversing the entire subtree rooted at this node; it is O(n) in the number of descendants rather than a constant-time field read. Cache the result when reading it repeatedly in a hot path.

IsLeaf

Gets a value indicating whether this node has no children.

public bool IsLeaf { get; }

Property Value

bool

true if the node is a leaf; otherwise, false.

IsRoot

Gets a value indicating whether this node has no parent.

public bool IsRoot { get; }

Property Value

bool

true if the node is a root; otherwise, false.

Parent

Gets the parent node, or null when this node is a root.

public Tree<T>? Parent { get; }

Property Value

Tree<T>

The parent node, or null.

Value

Gets or sets the value stored at this node.

public T Value { get; set; }

Property Value

T

The node's value.

Methods

AddChild(Tree<T>)

Attaches an existing detached subtree as a child of this node.

public void AddChild(Tree<T> child)

Parameters

child Tree<T>

The subtree to attach.

Exceptions

ArgumentNullException

child is null.

InvalidOperationException

child already has a parent, or attaching it would create a cycle.

AddChild(T)

Creates a new child node with the specified value and appends it to this node's children.

public Tree<T> AddChild(T value)

Parameters

value T

The value of the new child node.

Returns

Tree<T>

The newly created child node.

Ancestors()

Enumerates the ancestors of this node, from its parent up to the root.

public IEnumerable<Tree<T>> Ancestors()

Returns

IEnumerable<Tree<T>>

A lazily evaluated sequence of ancestor nodes.

Clear()

Detaches all children from this node.

public void Clear()

Descendants()

Enumerates every descendant of this node in pre-order, excluding this node itself.

public IEnumerable<Tree<T>> Descendants()

Returns

IEnumerable<Tree<T>>

A lazily evaluated sequence of descendant nodes.

Leaves()

Enumerates the leaf nodes of the subtree rooted at this node.

public IEnumerable<Tree<T>> Leaves()

Returns

IEnumerable<Tree<T>>

A lazily evaluated sequence of leaf nodes.

LevelOrder()

Enumerates the subtree rooted at this node in level (breadth-first) order.

public IEnumerable<Tree<T>> LevelOrder()

Returns

IEnumerable<Tree<T>>

A lazily evaluated breadth-first sequence beginning with this node.

PostOrder()

Enumerates the subtree rooted at this node in post-order: each node is visited after its children, which are visited left to right.

public IEnumerable<Tree<T>> PostOrder()

Returns

IEnumerable<Tree<T>>

A lazily evaluated post-order sequence ending with this node.

PreOrder()

Enumerates the subtree rooted at this node in pre-order: each node is visited before its children, which are visited left to right.

public IEnumerable<Tree<T>> PreOrder()

Returns

IEnumerable<Tree<T>>

A lazily evaluated pre-order sequence beginning with this node.

Remove()

Detaches this node from its parent.

public bool Remove()

Returns

bool

true if the node was detached; false if it was already a root.

RemoveChild(Tree<T>)

Detaches the specified child from this node.

public bool RemoveChild(Tree<T> child)

Parameters

child Tree<T>

The child to detach.

Returns

bool

true if the child was found and detached; otherwise, false.

Exceptions

ArgumentNullException

child is null.

Root()

Returns the root of the tree containing this node.

public Tree<T> Root()

Returns

Tree<T>

The topmost ancestor, or this node when it is already a root.

Applies to

Product	Versions
.NET	8, 10