Data Structure Trees in Ruby

2 Min. Read
Sep 16, 2019

What is tree data structure?

Tree is a non- linear data structure where data are arranged in a hierarchy. Here non-linear means each data in a tree can have different items in relation to it and the number of item related to each data also varies. Also, the structure of tree follow some kind of hierarchy so it is called a hierarchical structure. In general, tree data structure is like a tree in nature having root, leaves, branches etc. Each tree has a single root. All other nodes further extend from the root and its descendents. The node which do not have any descendents is called leaf.

Types of trees

  1. Binary Tree
  2. Binary Search Tree

Binary Tree is a tree where each node have at most two child nodes. Binary Search tree is a tree where each value is unique, the left sub tree of a node only contains value less than the node and right sub tree contains only values greater than the node. Today, I will be talking details about Binary Tree only.

Binary Tree

A binary tree is a tree data structure in which each node has at most two children, which are called as the left child and the right child node. In binary tree, we can sort a tree such that a node has all its smaller nodes towards left side and greater nodes towards right. Lets create a binary tree,

At first lets create a Node class

1
2
3
4
5
6
7
8
9

class Node
 attr_reader :value
 attr_accessor :left, :right
 def initialize(value)
  @value = value
  @left =nil
  @right =nil
 end
end

Here, left pointer points to left child node and right pointer to the right child node of each node. Now, lets code to add some values to the tree, ruby def pushNode(node, value) if(value > node.value) if(node.right) pushNode(node.right, value) else node.right = Node.new(value) end else if(node.left) pushNode(node.left, value) else node.left = Node.new(value) end end end From this code, smaller values goes to left and bigger or equal values goes to the right of each node. Recursive function is one of easy ways to work with binary tree. So, here we use recursive function to add values.

1
2
3

arr = [5,6,2,4,1,8,7,9,3];
root = Node.new(arr.shift);
arr.each{|e| pushNode(root, e) }

Here, we set the first element of array as our root element. Then, we run pushNode function to populate the tree from the array. Hence, we have now created an binary tree having smaller values on the left and bigger values on the right. In, this way we can create binary tree in ruby.

Summary

Binary tree in ruby is very useful. It is effective for sorting a data structure easily and useful to understand data structures in Ruby.