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: