philiprehberger-tree

Generic tree data structure with traversal, search, and serialization

Requirements

• Ruby >= 3.1

Installation

Add to your Gemfile:

gem "philiprehberger-tree"

Or install directly:

gem install philiprehberger-tree

Usage

require "philiprehberger/tree"

root = Philiprehberger::Tree::Node.new('root')
child = root.add_child('child')
child.add_child('grandchild')

root.size      # => 3
root.height    # => 2
root.leaf?     # => false
child.depth    # => 1

Traversal

root.each_dfs { |node| puts node.value }        # depth-first pre-order
root.each_bfs { |node| puts node.value }        # breadth-first
root.each_post_order { |node| puts node.value } # depth-first post-order

Search and Path Finding

node = root.find { |n| n.value == 'grandchild' }
path = root.path_to('grandchild')
path.map(&:value)  # => ['root', 'child', 'grandchild']

Value Lookup

root.find_by_value('grandchild')   # => #<Node value="grandchild">
root.find_by_value('missing')      # => nil
root.include?('grandchild')        # => true
root.include?('missing')           # => false

Select Matching Nodes

matches = root.select { |n| n.value.to_s.start_with?('g') }
matches.map(&:value)  # => ['grandchild'] (DFS pre-order)

Deserialization

hash = { value: 'root', children: [{ value: 'child', children: [] }] }
tree = Philiprehberger::Tree::Node.from_h(hash)
tree.value  # => 'root'

Map (Transform Values)

mapped = root.map { |v| v.upcase }
mapped.value                     # => 'ROOT'
mapped.children.map(&:value)     # => ['CHILD']

Flatten

root.flatten  # => ['root', 'child', 'grandchild'] (DFS pre-order)

Iterate with Depth

root.each_with_depth do |node, depth|
  puts "#{'  ' * depth}#{node.value}"
end

Serialization

root.to_h
# => { value: 'root', children: [{ value: 'child', children: [...] }] }

puts root.print_tree
# root
# └── child
#     └── grandchild

Subtree Extraction

copy = child.subtree  # deep copy, detached from parent
copy.parent           # => nil

Equality

tree1 = Philiprehberger::Tree::Node.new('a')
tree2 = Philiprehberger::Tree::Node.new('a')
tree1 == tree2  # => true (structural equality)

Ancestors and Siblings

grandchild.ancestors.map(&:value)  # => ['child', 'root']
child.siblings.map(&:value)        # => ['other_child']

Sibling Navigation

a = root.add_child('a')
b = root.add_child('b')
c = root.add_child('c')

b.next_sibling.value  # => 'c'
b.prev_sibling.value  # => 'a'
a.prev_sibling        # => nil (first child)
c.next_sibling        # => nil (last child)

Leaf Collection

root.leaves.map(&:value)  # => ['grandchild']

All Root-to-Leaf Paths

root.paths.map { |path| path.map(&:value) }
# => [['root', 'child', 'grandchild']]

Pruning Deep Subtrees

# max_depth: 0 drops every child
root.prune(max_depth: 0)
root.children  # => []

# max_depth: 1 keeps immediate children, drops grandchildren
root.prune(max_depth: 1)

# Returns self for chaining
root.prune(max_depth: 2).flatten

API

Node

Method	Description
.new(value)	Create a new tree node
.from_h(hash)	Reconstruct a tree from a hash (inverse of #to_h)
#add_child(value)	Add a child node and return it
#remove_child(value)	Remove a child by value
#prune(max_depth:)	Remove descendants deeper than max_depth below receiver (returns self)
#children	Array of child nodes
#parent	Parent node or nil
#root?	True if node has no parent
#leaf?	True if node has no children
#depth	Distance from root
#height	Height of subtree
#size	Total nodes in subtree
#each_dfs	Depth-first pre-order iteration
#each_bfs	Breadth-first iteration
#each_post_order	Depth-first post-order iteration
#find { |n| }	Find first node matching predicate
#find_by_value(value)	Find first node whose value equals value
#include?(value)	True if any node has the given value
#select { |n| }	All nodes matching predicate (DFS pre-order)
#path_to(value)	Array of nodes from root to target
#leaves	All leaf nodes in subtree
#paths	All root-to-leaf paths as arrays of nodes (DFS pre-order)
#subtree	Deep copy of node and descendants
#==	Structural equality comparison
#ancestors	Array of ancestors from parent to root
#siblings	Sibling nodes excluding self
#next_sibling	Next sibling in parent's child order, or nil
#prev_sibling	Previous sibling in parent's child order, or nil
#map { |value| }	New tree with transformed values
#flatten	All values as flat array (DFS pre-order)
#each_with_depth	Iterate yielding node and depth level
#to_h	Serialize subtree to hash
#print_tree	Visual string representation

Development

bundle install
bundle exec rspec
bundle exec rubocop

Support

If you find this project useful:

⭐ Star the repo

🐛 Report issues

💡 Suggest features

❤️ Sponsor development

🌐 All Open Source Projects

💻 GitHub Profile

🔗 LinkedIn Profile

License

MIT