Tree Data Structure

Trees are hierarchical structures used in computer science to organize and represent data. They are made up of nodes connected by edges and can be used to solve a variety of problems. Trees can be applied in many fields, including computer science, biology, and linguistics. In this article, we will explore the components and properties of trees, how to implement them, and their applications in various fields.

What is a Tree?

A tree is a hierarchical structure that is made up of nodes and edges. The topmost node is called the root node, and it has no parent. The other nodes in the tree are connected by edges and are either internal nodes (nodes that have one or more child nodes) or leaf nodes (nodes that have no children).

Each node in a tree can have zero or more child nodes. The number of children a node can have is called the degree of the node. A node with no children is called a leaf node, while a node with one or more children is called an internal node. The edges in a tree represent the relationships between nodes.

The Components of a Tree

There are several components of a tree, including the root node, internal nodes, leaf nodes, edges, and subtrees. Let’s take a closer look at each of these components.

1. Root Node: The root node is the topmost node in the tree, and it has no parent. It is the starting point of the tree.
2. Internal Nodes: Internal nodes are nodes that have one or more child nodes. They are used to represent the intermediate stages of a process or to group related nodes together.
3. Leaf Nodes: Leaf nodes are nodes that have no children. They are used to represent the end points of a process or to store data.
4. Edges: Edges are the connections between nodes. They represent the relationships between nodes in the tree.
5. Subtrees: A subtree is a smaller tree within a larger tree. It consists of a node and all its descendants.

The Properties of a Tree

There are several properties of a tree, including depth, height, degree, and balance. Let’s take a closer look at each of these properties.

1. Depth: The depth of a node is the number of edges from the root node to that node. The depth of the root node is 0.
2. Height: The height of a node is the number of edges from that node to the deepest leaf node. The height of a leaf node is 0.
3. Degree: The degree of a node is the number of children that the node has.
4. Balance: A tree is balanced if the difference between the height of its left and right subtrees is at most 1. A balanced tree is important for efficient searching and insertion operations.

How to Implement a Tree

There are several ways to implement a tree, including using linked lists, arrays, and classes. Let’s take a closer look at each of these implementation methods.

1. Linked Lists: In this implementation method, each node in the tree is represented as a struct or class that contains a data field and a pointer to its children nodes. The children nodes are also represented as nodes with their own data fields and pointers to their children nodes.

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;
    
    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    
    return 0;
}

class Node {
    int data;
    Node leftChild;
    Node rightChild;

    public Node(int data) {
        this.data = data;
        this.leftChild = null;
        this.rightChild = null;
    }
}

public class BinaryTree {
    Node root;

    public BinaryTree(int data) {
        root = new Node(data);
    }

    public BinaryTree() {
        root = null;
    }

    public void insert(int data) {
        Node newNode = new Node(data);
        if (root == null) {
            root = newNode;
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node current = queue.remove();
            if (current.leftChild == null) {
                current.leftChild = newNode;
                return;
            } else if (current.rightChild == null) {
                current.rightChild = newNode;
                return;
            } else {
                queue.add(current.leftChild);
                queue.add(current.rightChild);
            }
        }
    }
}

class Node {
  constructor(data) {
    this.data = data;
    this.children = [];
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  add(data, parentNode) {
    const node = new Node(data);
    if (!parentNode) {
      this.root = node;
    } else {
      parentNode.children.push(node);
    }
    return node;
  }
}

2. Arrays: In this implementation method, the tree is represented as an array of nodes, where each node contains a data field and an index that points to its parent node and its children nodes.

#include <iostream>
#include <vector>

using namespace std;

class Node {
public:
    int data;
    int parentIndex;
    vector<int> childrenIndices;
    
    Node(int val, int parent) {
        data = val;
        parentIndex = parent;
    }
};

int main() {
    vector<Node> tree = {
        {1, -1, {1, 2}},    // root node at index 0
        {2, 0, {3, 4}},     // children of root node at indices 1 and 2
        {3, 1, {}},         // leaf node at index 3
        {4, 1, {5, 6}},     // children of node 2 at indices 4 and 5
        {5, 4, {}},         // leaf node at index 6
        {6, 4, {}},         // leaf node at index 7
    };
    
    return 0;
}

public class BinaryTree {
    int[] tree;
    int currentSize;

    public BinaryTree(int capacity) {
        tree = new int[capacity];
        currentSize = 0;
    }

    public boolean insert(int data) {
        if (currentSize == tree.length) {
            return false;
        }
        tree[currentSize] = data;
        int index = currentSize;
        int parentIndex = (index - 1) / 2;
        while (index > 0 && tree[index] < tree[parentIndex]) {
            int temp = tree[index];
            tree[index] = tree[parentIndex];
            tree[parentIndex] = temp;
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
        currentSize++;
        return true;
    }
}

class Node {
  constructor(data) {
    this.data = data;
    this.parentIndex = -1;
    this.childIndexes = [];
  }
}

class Tree {
  constructor() {
    this.nodes = [];
  }

  add(data, parentIndex) {
    const node = new Node(data);
    node.parentIndex = parentIndex;
    this.nodes.push(node);
    if (parentIndex >= 0) {
      this.nodes[parentIndex].childIndexes.push(this.nodes.length - 1);
    }
    return node;
  }
}

3. Classes: In this implementation method, the tree is represented as a class that contains a data field, a pointer to its parent node, and pointers to its children nodes.

#include <iostream>
#include <vector>

using namespace std;

class Node {
public:
    int data;
    Node* parent;
    vector<Node*> children;
    
    Node(int val, Node* p) {
        data = val;
        parent = p;
    }
};

int main() {
    Node* root = new Node(1, nullptr);
    root->children.push_back(new Node(2, root));
    root->children.push_back(new Node(3, root));
    root->children[0]->children.push_back(new Node(4, root->children[0]));
    root->children[0]->children.push_back(new Node(5, root->children[0]));
    root->children[1]->children.push_back(new Node(6, root->children[1]));
    root->children[1]->children.push_back(new Node(7, root->children[1]));
    
    return 0;
}

class Node {
    int data;
    Node leftChild;
    Node rightChild;
    Node parent;

    public Node(int data) {
        this.data = data;
        this.leftChild = null;
        this.rightChild = null;
        this.parent = null;
    }
}

public class BinaryTree {
    Node root;

    public BinaryTree(int data) {
        root = new Node(data);
    }

    public BinaryTree() {
        root = null;
    }

    public Node insert(int data, Node parent) {
        Node newNode = new Node(data);
        newNode.parent = parent;
        if (root == null) {
            root = newNode;
            return root;
        }
        if (parent.leftChild == null) {
            parent.leftChild = newNode;
            return parent.leftChild;
        } else if (parent.rightChild == null) {
            parent.rightChild = newNode;
            return parent.rightChild;
        } else {
            Node leftResult = insert(data, parent.leftChild);
            if (leftResult != null) {
                return leftResult;
            } else {
                return insert(data, parent.rightChild);
            }
        }
    }
}

class Node {
  constructor(data, parent = null) {
    this.data = data;
    this.parent = parent;
    this.children = [];
  }

  addChild(data) {
    const child = new Node(data, this);
    this.children.push(child);
    return child;
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  add(data) {
    if (!this.root) {
      this.root = new Node(data);
      return this.root;
    } else {
      return this.root.addChild(data);
    }
  }
}

Applications of Trees

Trees have a variety of applications in computer science and other fields, including:

1. Data Storage and Retrieval: Trees are commonly used to store and retrieve data efficiently. Binary search trees, AVL trees, and B-trees are some examples of trees that are used in data storage and retrieval systems. These trees allow fast searching, insertion, and deletion of data.

For instance, in a database management system, an index is created using a B-tree data structure to provide quick access to the data stored in a table. A B-tree is chosen over other data structures because it is a balanced tree that can handle a large number of data entries and allows efficient insertion and deletion of data.

2. File Systems: Trees are also used in file systems to organize files and directories. The file system tree starts with the root directory and branches out to subdirectories and files. This hierarchical organization enables easy navigation and manipulation of files and directories.

For example, in the Windows operating system, the file system is organized in a tree-like structure with the root directory being the “C:\” drive. Users can navigate through the file system by selecting directories and files from the tree structure.

3. Decision Making: Decision trees are used in machine learning to model decisions and their possible consequences. The tree starts with a decision node and branches out to possible outcomes based on the decision. Decision trees are commonly used in finance, medicine, and business to make complex decisions.

For example, a bank may use a decision tree to determine whether to approve a loan application based on various factors such as income, credit score, and employment status.

4. Compiler Design: Trees are used in compiler design to represent the syntax of a programming language. A syntax tree, also known as a parse tree, is a tree-like representation of the structure of a program. This representation helps the compiler in parsing the program and generating an executable code.

For instance, the syntax tree for a simple “Hello World” program in C programming language would consist of nodes representing the “printf” function call, the string “Hello World”, and the main function.

5. Internet Routing: Trees are also used in internet routing to determine the best path for data to travel from one network to another. The Border Gateway Protocol (BGP) uses a tree-like structure called a routing table to store information about the available paths to a particular network.

For example, when a user types a URL in a web browser, the browser sends a request to the server through a series of routers. The routers use the routing table to determine the best path for the data to travel to reach the server.