Trees

excerpt: This covers the basics of building trees with two and many children.

Trees are recursive data structures that is used to store hierarchical data and model decision processes. For example, a company organizational chart can be stored in a tree. This article explains how to build simple trees and the basics to understand more complicated trees. A tree can be defined recursively:

• A single root node
• A root node connected by branches to one or more smaller trees

A binary tree has two children. It is useful in modeling problems with binary choices.

Building Trees

A tree’s node can be represented by using a class.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

node = Node.new(10)
p node.value

The value attribute stores the value of the node. The left and right children can be set to instances of node class. The constructor takes the value parameter and saves it in the value property. The node object is created by creating an instance of the Node class. The value stored in the node is printed. This class can be used to build the tree.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

root = Node.new(4)
node1 = Node.new(1)
node2 = Node.new(2)
node3 = Node.new(3)
node4 = Node.new(4)

root.left = node1
root.right = node2
node1.left = node3
node1.right = node4

The root node is created first, then the nodes for the left and right child of the nodes are created. The left child of the root is set to node3 and the right child is set to node4.

A tree with more than two children can be stored in an array or some other collection. The program can loop through the collection and perform some work on each children node. The Node class that defines an attribute for children is shown below.

1
2
3
4
5
6
7
8
9

class Node
  attr_reader :value
  attr_accessor :children
  
  def initialize(value)
    @value = value
    @children = []
  end
end

The only difference in this version of node class is that the children are stored in an array and it can be accessed through the children attribute.

Trees are useful for storing and manipulating hierarchical data. The values in a tree can be enumerated in different orders and search for values within the tree.

If the tree is wide, its height is O(log N) and the performance is faster. If the tree is tall then the height is O(N) and this affects performance. Building a binary search tree takes O(N log N) time in the best case and quadratic time in the worst case.