Trees in Ruby

Ruby Devs
Ruby Devs
Aug 31, 2018 · 3 min read

As wikipedia puts it, In computer science, a tree is an abstract data type (ADT) — or data structure implementing this ADT — that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

Ruby is excellent as a language, and you can create trees via a really short code. Here, we are creating a binary tree.

To initialise a tree just do, tree = Tree.new(3)

Now we can assume that every node as a tree in itself, this way we can create a complete binary tree.
tree.left = Tree.new(1)
tree.right = Tree.new(10)
tree.left.left = Tree.new(0)
tree.right.right = Tree.new(100)
tree.right.right.right = Tree.new(1000)

Tree created

There are various traversal like depth first and breadth first, depth first further includes three traversals namely, preorder, postorder and inorder.

Inorder will print like Left, Root, Right — 0,1,3,10,100,1000

Preorder will follow the order Root, Left, Right — 3,1,0,10,100,1000

Postorder will follow Left, Right, Root — 0,1,1000,100,10,3

Sometimes we have to calculate the height of a tree, there we can use this piece of code.

So we return whatever is maximum of the height of left and right subtrees.

Suppose a question is given where you have to print all paths from root to leaf.

https://gist.github.com/credi-himanshu/8d0c6fa3038bb313655b2e70ca573d40

Sometimes you may have to calculate the maximum distance between the two nodes in a tree. Which is very interesting. If the max passes through the root, then we have to calculate the left_height+right_height+1, else the max could be present in the left subtree or right subtree.

One question could be to check if the given tree is a binary search tree(bst) or not, now BST has a property that all nodes to the left are smaller and all nodes to the right are greater than the node itself. In max_value function below in base condition, you have to choose a large negative number.

The examples taken above all have dealt with the depth first traversal(dft). There is another traversal technique i.e. breadth first traversal technique, it makes the use of queues, lets see that now.

We are using the queue data structure to store level info, we enqueue the tree root node , as one dequeues from queue, we make sure that we add the children if present on the queue, so that we can further process them and until nothing is present in the queue.

Say now we want to see the tree on a vertical order.

Vertical Order Binary Tree

Now the hash calculated in the vertical order tree can be used to solve two problems.

  1. Vertical Order Tree
  2. Bottom View of a Tree

hash value ={0=>[1, 5, 6], -1=>[2], 1=>[3, 10], -2=>[4], 2=>[7], 3=>[11]}

Now for vertical order, just sort the keys according to keys, using hash.sort.to_h, which gives us

{-2=>[4], -1=>[2], 0=>[1, 5, 6], 1=>[3, 10], 2=>[7], 3=>[11]}

Just print the values while looping through the hash, and we get the vertical order tree.

Now for the bottom order — After sorting, just select the last value from each hash.

new_hash ={}

hash.sort.to_h.each{|k,v| new_hash[k] = v.last}

Just print the values while looping through the hash, and we get the bottom order tree.

{-2=>4, -1=>2, 0=>6, 1=>10, 2=>7, 3=>11}

The things we encounter daily as rubyists and sometimes while switching jobs :p

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade