Trees in Ruby
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)

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.

Now the hash calculated in the vertical order tree can be used to solve two problems.
- Vertical Order Tree
- 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}
