Binary Tree Implementation in Ruby

1. Introduction

A Binary Tree is a hierarchical data structure in which each node has at most two children, often referred to as the left and right child. It is a special case of a tree where each node has a maximum of two children. Binary trees are frequently used as a means for hierarchical data representation, including use cases like binary search trees, heap trees, syntax trees, and many more.

2. Implementation Steps

1. Define a Node class with attributes value, left, and right.

2. Initialize a BinaryTree class with a root node.

3. Implement the insert method to add nodes to the tree.

4. Implement a display method to print the tree in an in-order traversal.

5. Optionally, implement methods for pre-order, post-order, and level-order traversal.

3. Implementation in Ruby Programming

class Node
    attr_accessor :value, :left, :right
    def initialize(value)
        @value = value
        @left = nil
        @right = nil
    end
end
class BinaryTree
    def initialize
        @root = nil
    end
    # Insert value into the tree
    def insert(value)
        @root = insert_recursive(@root, value)
    end
    # Display tree in in-order traversal
    def display
        display_recursive(@root)
    end
    private
    def insert_recursive(node, value)
        return Node.new(value) if node.nil?
        if value < node.value
            node.left = insert_recursive(node.left, value)
        elsif value > node.value
            node.right = insert_recursive(node.right, value)
        end
        node
    end
    def display_recursive(node)
        return if node.nil?
        display_recursive(node.left)
        puts node.value
        display_recursive(node.right)
    end
end
# Client code
bt = BinaryTree.new
bt.insert(50)
bt.insert(30)
bt.insert(70)
bt.insert(20)
bt.insert(40)
bt.insert(60)
bt.insert(80)
puts "In-order traversal of binary tree:"
bt.display

Output:

In-order traversal of binary tree:
20
30
40
50
60
70
80

Explanation:

1. The Node class represents each element in the binary tree. Each node has a value, a left child, and a right child.

2. The BinaryTree initializes with a root node set to nil.

3. The insert method inserts a new value into the tree by invoking a recursive helper function insert_recursive. If the current node is empty, it places the new value there. If the value is less than the current node's value, it continues to the left child; if greater, it continues to the right child.

4. The display method prints the tree values in an in-order (left, root, right) sequence by invoking the recursive helper function display_recursive.

5. The private helper functions insert_recursive and display_recursive facilitate the recursive nature of binary tree operations.