Ruby Programming Tutorial - Lesson 32 - Recursion and Binary Trees

In this article we are going to learn about binary Tree data structure

Before we go learn it, we should be familiar with Recursion, and recursive methods.
so lets learn them first :)

What is Recursion ?

Recursion is a process in which a function calls itself as a subroutine. This allows the function to be repeated several times, since it calls itself during its execution. Functions that incorporate recursion are called recursive functions.

Recursion is often seen as an efficient method of programming since it requires the least amount of code to perform the necessary functions. However, recursion must be incorporated carefully, since it can lead to an infinite loop if no condition is met that will terminate the function.

Condition that makes it terminate is called "Base condition".

Lets have a look at a simple recursion

def factorial(x)
   if x == 1
      return x
   else
      return x*factorial(x-1)
   end
end

if you will call this method

puts factorial(5)

If want to learn more about Recursion or recursive methods, search for it :) Its good idea to have a strong base on this topic before proceeding further.

Binary Trees Data Structure

Tree is a data structure, which also consists upon nodes but nodes are connected in a way that every node has two children nodes, left and right, that is why they are called binary trees.

Each node can have 1, 2 or 0 children ..
Every Binary tree has a root node, or some people call it parent node.
Every Binary tree has leaf nodes, nodes which don't have any child nodes

Lets start by Identifying Entities

After learning about binary trees we came to conclusion that a binary tree consists upon two entities.

• Node
• Tree that consists upon nodes

A binary tree node has three properties, it has a reference to left child, right child and a data variable
So we can create a class to represent it like so.

class Node
    attr_accessor :val, :left, :right
  
    def initialize(val, left_node, right_node)
        @val   = val
        @left  = left_node
        @right = right_node
    end
end

After creating Node We are ready to use it and implement Binary Tree

require_relative 'node'

class Tree
    attr_accessor :root
  
    def initialize(val)
        @root = Node.new(val, nil, nil)
    end

    def insert_node(val, current)
        puts val[:id]
        if current == nil
            puts "base condition"
            return Node.new(val, nil, nil)
        end

        if val[:id] < current.val[:id]
            puts "going left"
            current.left = insert_node(val, current.left)
        else
            puts "going right"
            current.right = insert_node(val, current.right)
        end
    end
    def traverse(node)
        _node = node
        if(_node == nil)
            return 
        end
        puts _node.val
        traverse(_node.left)
        traverse(_node.right)
    end

end

You can see that, our Binary Tree has three methods.

• initialize
• insert_node
• traverse

First method allows us to create a root node, when a tree object is created from it.
Notice that when a tree object is initialized, it creates a root node, which has no children nodes. e.g it's left and right children nodes are nil ...

lets see how we are using this Tree class in main.rb

require_relative 'tree'
require_relative 'node'

_data = {id: 5000, name: "bilalhaider", age: 27, reward: 500}
_myTree = Tree.new(_data)

while $entry.to_i != 3
    print "1 - Insert new Node\n2 - Traverse tree\n3 - Exit\n Your Choice: "
    $entry = gets.chomp 
    _random = Random.new.rand(1..10000)

    if $entry.to_i == 1
        print "Insert your Name: "
        _username = gets.chomp
        
        print "Insert your age: "
        _age      = gets.chomp

        _data = {id: _random, name: _username, age: _age, reward: 500}
        puts "Data to be inserted in node #{_data}"

        _myTree.insert_node(_data, _myTree.root)
    elsif $entry.to_i == 2
        puts _myTree.traverse(_myTree.root)
    elsif $entry.to_i == 3
        puts "Exiting .... "
    else 
        puts "Invalid choice "
    end
end

Notice that, our Second Method(insert_node) in Tree class uses Recursion, and finds perfect spot for New node, where it can be inserted.. New node that is created from user's input :)

What is perfect location for a new node?
We have few rules for that .. These rules help us, later on for searching a record.

• every left node's id value is lower than its parent node's id value.
• every right node's id value is greater than its parent node's id value.

Take a look at following picture, for a better understanding :)

There you go my friends, you have implemented a data structure which is best when it comes to retrieving a recored of a user.

If you have 8 million records of users, it will take only 23 comparisons and you will reach your record :)

When using linked list, you may need to compare, or traverse the list and perform 8 million comparisons in its worst case to reach your record

Same number of steps required when adding a record, so binary trees will help you save time.