Tree basics

My worthy friend, gray are all theories,
And green alone Life's golden tree.

Johann Wolfgang von Goethe, Faust

Introduction

In the realm of computer science and data structures, trees play a vital role in organizing and storing data efficiently. A tree is a hierarchical data structure composed of nodes connected by edges. It looks like the structure of a real-world tree, with a root node at the top and branching nodes extending downwards.

Trees provide a flexible and efficient way to show relationships between elements. They are widely used in areas like databases, file systems, artificial intelligence, and network routing algorithms. One of the key features of trees is their hierarchical nature. The root node is the starting point, and from there, nodes branch into child nodes, forming a parent-child relationship. Each node can have zero or more children, except for the leaf nodes, which have no children. This hierarchical structure allows for quick searching, inserting, and deleting.

In this topic, we will delve into the basics of trees, including their structure, traversal techniques, and different types. We will explore binary trees, balanced trees, and other variations, discussing their properties. By the end of this topic, you will have a solid foundation in understanding and working with trees, enabling you to solve complex problems and optimize data organization in your programming.

Tree traversal techniques

'Tree traversal' is the process of visiting each node in a tree data structure exactly once. There are several ways to go through and process the nodes of a tree. The two main methods are depth-first traversal and breadth-first traversal.

Depth-first traversal is named for how it prioritizes visiting nodes. Remember that the depth of a node is the number of edges from the root to that particular node. DFS can be split into three types: pre-order, in-order, and post-order. They all have a runtime complexity $O(n)$, where $n$ is a number of tree nodes.

1. Pre-order Traversal: In pre-order traversal, you visit the root node first, then go through the left subtree, and finally the right subtree. This order is often used to make a copy of the tree or to print the nodes in a certain order:

   print(root->value)
   preorder(root->left)
   preorder(root->right)
   

2. In-order Traversal: For in-order traversal, you first visit the left subtree, then the root node, and the right subtree. This order is commonly used for binary search trees, as it goes through the nodes in ascending order. You can also use it to get the elements of a binary tree in sorted order:

   inorder(root->left)
   print(root->value)
   inorder(root->right)
   

3. Post-order Traversal: In post-order traversal, you first go through the left subtree, then the right subtree, and finally the root node. This method is often used to delete nodes from a tree, as it makes sure a node's children are deleted before the node itself:

   postorder(root->left)
   postorder(root->right)
   print(root->value)
   

Look at the illustration showing the results for all three DFS types used on a given tree. Try to follow it step by step and notice the differences in the methods. Note that each time you call a traversal function, the current node becomes a new root for the next step of the search.

Breadth-first traversal, also known as level-order traversal, goes through a tree by visiting nodes at each level before going to the next. This way, nodes at the same level are visited before deeper ones, giving a breadth-first view of the tree's structure.

The BFS algorithm uses a queue to keep track of the nodes to visit. It starts by putting the root node in the queue. Then, it repeats a loop until the queue is empty. In each step, the algorithm takes a node from the front, visits it, and adds its children to the back of the queue. This process repeats until all nodes in the tree have been visited:

let q be queue
add root to q

while q != empty:
  current_node = q->front
  print(current_node->value)
  remove q->front from q
  
  //adding children to the rear of the queue
  if (current_node->left != empty) then
    add current_node->left to q

  if (current_node->right != empty) then
    add current_node->right to q

One application of breadth-first traversal is finding the shortest path between two nodes in a tree or graph. By traversing the tree level by level, breadth-first traversal can efficiently find the shortest path between two nodes by exploring nodes in order of their distance from the starting node. Another application is constructing a tree from a given list of nodes or elements. By using breadth-first traversal, you can systematically build the tree ensuring the correct hierarchical structure.

Types of trees

Understanding various types of trees is important for picking the right structure for your needs. In this section, we will go over several kinds of trees.

1. A binary tree is a tree where each node has no more than two children, called the left child and the right child. The binary tree is common because of its simplicity and how useful it is. It makes searching, inserting, and deleting efficient and is the base for many other tree structures and algorithms.

   Binary trees can be categorized further based on their properties. Some common variations include:

   • Full Binary Tree: A full binary tree is a binary tree where every node has zero or two children. Every node is either a leaf or an internal node with two child nodes.

   • Complete Binary Tree: A complete binary tree has all levels fully filled except possibly the last one, and all nodes are as far left as possible. In a complete binary tree, the last level is filled from left to right, making a balanced structure.

   • Perfect Binary Tree: A perfect binary tree is one where all internal nodes have two children, and all leaf nodes are at the same level. This means every level of the tree is full.

     

2. Balanced trees are a class of trees that keep a balanced structure to make sure the tree's height stays logarithmic with respect to the number of nodes. A quick reminder: the tree's height is the longest number of edges from the root to a leaf. Balancing a tree makes searching, inserting, and deleting consistently quick. There are various types of balanced trees, each with its own balancing method. Some well-known examples are:

   • AVL Trees: Named after Adelson-Velskii and Landis, these trees are self-balancing binary search trees. They store each node's 'balance factor', which is the difference in height between the left and right subtrees. When an insertion or deletion makes the tree unbalanced, AVL trees do rotations to fix it. The time complexity for basic operations (insert, search, delete): $O(\log n)$.

   • B-Trees: B-trees are balanced search trees often used in databases and file systems. They are good at handling large amounts of data and work efficiently with disk access. B-trees have multiple keys in each node and maintain balance by moving keys around and adjusting tree structure during insertions and deletions. The time complexity for basic operations (insert, search, delete): $O(\log n)$.

   • Red-Black Trees: Red-black trees are another type of self-balancing binary search tree. They ensure that the tree remains approximately balanced by following a set of color rules. Each node is colored red or black, and the tree is adjusted by rotating and changing colors to keep balanced. In fact, red-black trees are like a specific case of B-tree and are often used for some data structures like maps and sets. The time complexity for basic operations (insert, search, delete): $O(\log n)$.

3. Tries: Also called prefix trees, tries are special tree structures for fast string searching and getting data. They store keys associated with values, allowing fast prefix-based searches.

4. N-ary trees are generalizations of binary trees, with each node allowed to have more than two children. They're used for various purposes like showing layered data, parsing expressions, and managing file systems.

Of course, these tree types are not entirely separate. For example, balanced trees are often designed as N-ary trees for better and more logical data arrangement. Combining multiple tree types in one particualr programming solution makes one being able to get the most out of these powerful concepts.

Conclusion

To wrap up, trees are versatile structures that provide a way to store and organize data in a hierarchy. Knowing how to go through trees lets you process tree nodes efficiently, and different tree types like binary trees and balanced trees have specific benefits for different uses. Trees play a big part in many areas, including computer graphics, networking, and AI. Learn to use the power and flexibility of trees to boost your programming skills. Mastering tree basics equips you with the tools to solve tricky problems quickly. So, get into trees and see all they can do!