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