A TREE is a data structure used to represent hierarchical relationships between elements.
The TREES are a reduced version of an oriented GRAPH. Therefore, it is composed of interconnected nodes, where each node can have zero or more child nodes.
However, the TREE adds the restrictions that:
- Each node can only have one parent
- It is acyclic
In consequence, a TREE results in a structure that originates from a single node, and from there it branches out… just like a tree.
The node at the top is known as the root node. Each parent-child relationship is called a branch. Nodes without children are called leaves. And I think they’ve already run out of botanical similes 🌱
The TREES are a widely used structure, because they allow us to represent data hierarchically. By this we mean that each piece of data can contain other pieces of data.
Let’s give an example. The organization of files in a file system follows a tree structure. Each directory can contain files and subdirectories, and these in turn can contain others. And so on.
Another example, the organization chart of a company could be represented by a tree. Each node represents an employee or a department, and the hierarchical relationships between them are represented by the connections between the nodes.
More examples, the list of products available in an online store. Each node represents a category of products (for example, food, cleaning products, etc.) and the elements of each category are the individual products.
Finally, in web development, the Document Object Model (DOM) represents the structure of a web page as a tree. Where each HTML element is a node in the tree, and contains other elements inside it.
In other words, trees are one of the structures that you will most frequently use. So it is worth learning how to use it.
Components of a Tree
- Node: A node is a basic entity of a tree that can contain information and references to its child nodes
Root node: It is the main node of the tree, from which all other nodes branch out. A tree can only have one root node.
Leaf node: A leaf node is one that does not have child nodes. That is, it is the end of a branch in the tree.
Branch: It is each of the relationships between a parent node and its children.
Node level: The level of a node is its distance from the root node. The level of the root node is 0, and the level of the direct child nodes of the root node is 1, and so on.
Tree height: The height of a tree is the length of the longest path from the root to a leaf.
Subtree: A subtree is a set of nodes and edges that form a tree within a larger tree. Each node in a tree can be considered as the root of a subtree.
Types of Trees
Trees can be classified into several types based on their structure and the restrictions they impose. Some common types of trees include:
- N-ary Trees: In an N-ary tree, each node can have a variable number of children. This makes it more general than a binary tree.
- Binary Trees: A binary tree is one in which each node can have at most two child nodes, usually called left child and right child.
- Binary Search Trees: A binary search tree is a special type of binary tree in which for each node, the nodes in the left subtree have values less than the current node, and those in the right subtree have values greater than the current node. This makes it very suitable for searches.
DFS and BFS Search
When working with TREES, the first thing you will need is a way to traverse them. To access their nodes, to search for elements, for everything.
The two common algorithms for traversing trees are:
- DFS (Depth-First Search)
- BFS (Breadth-First Search)
Although these algorithms are called “search”, they are not only used to search for a node. They are used to traverse the tree and perform any operation on the nodes that we want.
There is no one better than the other, in some problems DFS will be better, in others BFS, and in many it won’t matter. Let’s take a look at them.
Depth-First Search (DFS)
This DFS method traverses the tree in depth, visiting all descendants of a node before moving on to the next sibling.
That is, suppose we want to perform an action on a node. I’m going to call it the action 🎇. For example, we want to initialize the value of each node, or search, or whatever.
The DFS is called “in depth”, because it prioritizes going down vertically. It takes the root of the tree and goes down as far as it can. Then it goes back, moves horizontally, and goes down as far as it can again.
Normally DFS is implemented as a simple recursive function:
- Start from the root node
- Call the recursive function 🔁 for each of its children
- Then perform
the action🎇 on the node
recursive_DFS(node, action)
{
// Traverse all the children of the current node
node.children.foreach(child => recursive_DFS(child, action));
// After visiting all the children, the action is applied to the current node
action(node);
}Breadth-First Search (BFS)
The BFS method traverses all nodes of a level, before moving on to the next level, visiting all neighbors of a node before continuing with the next level.
The BFS is called “in width”, because it prioritizes expanding horizontally. It takes the root of the tree and goes through all its children. Then it moves on to the next level, and processes all the nodes. It goes down levels until it’s done.
To implement a BFS, we will generally use an auxiliary collection, such as a list or a queue. The algorithm is:
- Start from the root node, put it in the queue
- While the queue is not empty
- Remove the first node, and perform
the action🎇 on it - Add all the children of this node to the queue
- Remove the first node, and perform
recursive_BFS(node, action)
{
queue = new Queue(); // Create a queue to store the nodes to be visited
queue.enqueue(node); // Add the root node to the queue
while (!queue.isEmpty()) { // While there are nodes in the queue
current = queue.dequeue(); // Remove the first node from the queue
action(current); // Apply the action to the current node
// Add the children of the current node to the queue
current.children.foreach(child => queue.enqueue(child));
}
}Example of Trees in different programming languages
Let’s see how to implement a non-binary tree in different programming languages:
using System;
using System.Collections.Generic;
class Node
{
public int Value { get; set; }
public List<Node> Children { get; set; }
public Node(int value)
{
Value = value;
Children = new List<Node>();
}
public void AddChild(Node child)
{
Children.Add(child);
}
public override string ToString()
{
return $"Node Value: {Value}";
}
}
class Tree
{
public Node Root { get; set; }
public Tree()
{
Root = null;
}
public void PrintTree(Node node, string indent = "")
{
if (node == null) return;
Console.WriteLine(indent + node.ToString());
if (node.Children != null)
{
foreach (var child in node.Children)
{
PrintTree(child, indent + " ");
}
}
}
public Node Search(int value, Node node)
{
if (node == null) return null;
if (node.Value == value) return node;
foreach (var child in node.Children)
{
var foundNode = Search(value, child);
if (foundNode != null) return foundNode;
}
return null;
}
public void DFS(Node node)
{
if (node == null) return;
Console.WriteLine(node.Value);
if (node.Children != null)
{
foreach (var child in node.Children)
{
DFS(child);
}
}
}
public void BFS()
{
if (Root == null) return;
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(Root);
while (queue.Count > 0)
{
Node current = queue.Dequeue();
Console.WriteLine(current.Value);
foreach (var child in current.Children)
{
queue.Enqueue(child);
}
}
}
}
class Program
{
static void Main(string[] args)
{
Tree tree = new Tree();
tree.Root = new Node(1);
tree.Root.AddChild(new Node(2));
tree.Root.AddChild(new Node(3));
tree.Root.Children[0].AddChild(new Node(4));
// Imprimir el árbol
Console.WriteLine("Árbol:");
tree.PrintTree(tree.Root);
// Buscar un valor en el árbol
int valueToFind = 4;
Node foundNode = tree.Search(valueToFind, tree.Root);
if (foundNode != null)
{
Console.WriteLine($"\nSe encontró el nodo con valor {valueToFind}: {foundNode}");
}
else
{
Console.WriteLine($"\nNo se encontró el nodo con valor {valueToFind}.");
}
// DFS
Console.WriteLine("\nRecorrido en Profundidad (DFS):");
tree.DFS(tree.Root);
// BFS
Console.WriteLine("\nRecorrido en Amplitud (BFS):");
tree.BFS();
}
}
#include <iostream>
#include <queue>
#include <vector>
class Node {
public:
int value;
std::vector<Node*> children;
Node(int val) : value(val) {}
void addChild(Node* child) {
children.push_back(child);
}
};
class Tree {
public:
Node* root;
Tree() : root(nullptr) {}
void printTree(Node* node, std::string indent = "") {
if (node == nullptr) return;
std::cout << indent << "Node Value: " << node->value << std::endl;
for (auto child : node->children) {
printTree(child, indent + " ");
}
}
Node* search(int value, Node* node) {
if (node == nullptr) return nullptr;
if (node->value == value) return node;
for (auto child : node->children) {
Node* foundNode = search(value, child);
if (foundNode != nullptr) return foundNode;
}
return nullptr;
}
void DFS(Node* node) {
if (node == nullptr) return;
std::cout << node->value << std::endl;
for (auto child : node->children) {
DFS(child);
}
}
void BFS() {
if (root == nullptr) return;
std::queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
std::cout << current->value << std::endl;
for (auto child : current->children) {
q.push(child);
}
}
}
};
int main() {
Tree tree;
tree.root = new Node(1);
tree.root->addChild(new Node(2));
tree.root->addChild(new Node(3));
tree.root->children[0]->addChild(new Node(4));
// Imprimir el árbol
std::cout << "Árbol:" << std::endl;
tree.printTree(tree.root);
// Buscar un valor en el árbol
int valueToFind = 4;
Node* foundNode = tree.search(valueToFind, tree.root);
if (foundNode != nullptr) {
std::cout << "\nSe encontró el nodo con valor " << valueToFind << ": Node Value: " << foundNode->value << std::endl;
} else {
std::cout << "\nNo se encontró el nodo con valor " << valueToFind << "." << std::endl;
}
// DFS
std::cout << "\nRecorrido en Profundidad (DFS):" << std::endl;
tree.DFS(tree.root);
// BFS
std::cout << "\nRecorrido en Amplitud (BFS):" << std::endl;
tree.BFS();
// Liberar memoria
delete tree.root->children[0]->children[0];
delete tree.root->children[0];
delete tree.root->children[1];
delete tree.root;
return 0;
}
class Node {
constructor(value) {
this.value = value;
this.children = [];
}
addChild(child) {
this.children.push(child);
}
}
class Tree {
constructor() {
this.root = null;
}
printTree(node, indent = "") {
if (node === null) return;
console.log(indent + "Node Value: " + node.value);
for (let child of node.children) {
this.printTree(child, indent + " ");
}
}
search(value, node) {
if (node === null) return null;
if (node.value === value) return node;
for (let child of node.children) {
let foundNode = this.search(value, child);
if (foundNode !== null) return foundNode;
}
return null;
}
DFS(node) {
if (node === null) return;
console.log(node.value);
for (let child of node.children) {
this.DFS(child);
}
}
BFS() {
if (this.root === null) return;
let queue = [this.root];
while (queue.length > 0) {
let current = queue.shift();
console.log(current.value);
for (let child of current.children) {
queue.push(child);
}
}
}
}
// Crear el árbol
let tree = new Tree();
tree.root = new Node(1);
tree.root.addChild(new Node(2));
tree.root.addChild(new Node(3));
tree.root.children[0].addChild(new Node(4));
// Imprimir el árbol
console.log("Árbol:");
tree.printTree(tree.root);
// Buscar un valor en el árbol
let valueToFind = 4;
let foundNode = tree.search(valueToFind, tree.root);
if (foundNode !== null) {
console.log(`\nSe encontró el nodo con valor ${valueToFind}: Node Value: ${foundNode.value}`);
} else {
console.log(`\nNo se encontró el nodo con valor ${valueToFind}.`);
}
// DFS
console.log("\nRecorrido en Profundidad (DFS):");
tree.DFS(tree.root);
// BFS
console.log("\nRecorrido en Amplitud (BFS):");
tree.BFS();
class Node:
def __init__(self, value):
self.value = value
self.children = []
def add_child(self, child):
self.children.append(child)
class Tree:
def __init__(self):
self.root = None
def print_tree(self, node, indent=""):
if node is None:
return
print(indent + "Node Value: " + str(node.value))
for child in node.children:
self.print_tree(child, indent + " ")
def search(self, value, node):
if node is None:
return None
if node.value == value:
return node
for child in node.children:
found_node = self.search(value, child)
if found_node is not None:
return found_node
return None
def dfs(self, node):
if node is None:
return
print(node.value)
for child in node.children:
self.dfs(child)
def bfs(self):
if self.root is None:
return
queue = [self.root]
while queue:
current = queue.pop(0)
print(current.value)
for child in current.children:
queue.append(child)
# Crear el árbol
tree = Tree()
tree.root = Node(1)
tree.root.add_child(Node(2))
tree.root.add_child(Node(3))
tree.root.children[0].add_child(Node(4))
# Imprimir el árbol
print("Árbol:")
tree.print_tree(tree.root)
# Buscar un valor en el árbol
value_to_find = 4
found_node = tree.search(value_to_find, tree.root)
if found_node is not None:
print(f"\nSe encontró el nodo con valor {value_to_find}: Node Value: {found_node.value}")
else:
print(f"\nNo se encontró el nodo con valor {value_to_find}.")
# DFS
print("\nRecorrido en Profundidad (DFS):")
tree.dfs(tree.root)
# BFS
print("\nRecorrido en Amplitud (BFS):")
tree.bfs()