Tree
A tree is a hierarchical data structure used in computer science to represent data in a parent-child relationship. Starting from a root node, each node can branch out to multiple child nodes, forming a structure that resembles a tree. This makes trees ideal for representing hierarchical data like organizational charts, file systems, and more. Trees allow for efficient searching, insertion, and deletion operations, making them fundamental in various algorithms and applications.
Tree Terminologies
- Node: The fundamental element of a tree that contains data and links to other nodes. Each node can have multiple children.
- Root: The topmost node of a tree, which has no parent. It is the starting point of the tree structure.
- Edge: A connection between two nodes, representing the parent-child relationship.
- Leaf: A node that does not have any children. Leaves are the end nodes of the tree.
- Internal Node: A node that has at least one child. These nodes are neither the root nor leaves and form the intermediate structure of the tree.
- Height of a Node: The length of the longest path from the node to a leaf. The height of a tree is the height of its root.
- Depth of a Node: The length of the path from the root to the node. It indicates the level at which the node is located in the tree.
- Level: All nodes at the same depth. For example, all nodes at depth 2 form level 2.
- Degree of a Node: The number of children a node has. The degree of the tree is the maximum degree of any node in the tree.
- Parent Node: A node that has one or more children, establishing the parent-child relationship.
- Child Node: A node that is connected to a parent node.
- Sibling: Nodes that share the same parent, making them peers within the tree structure.
Binary Tree
A binary tree is a specific type of tree data structure in which each node has at most two children, referred to as the left child and the right child. This restriction makes binary trees simpler and more efficient for many algorithms, allowing for clear and efficient traversal, insertion, and deletion processes.
When discussing trees in data structures, binary trees often take center stage due to the following reasons:
Simplicity and Efficiency: Binary trees are simple to implement and provide efficient means for data operations. Their structure allows for straightforward recursive algorithms for traversal, insertion, and deletion.
Binary Search Trees (BSTs): BSTs are a type of binary tree where the left child contains values less than the parent node, and the right child contains values greater than the parent node. This property enables efficient searching, insertion, and deletion operations, with an average time complexity of O(log n).
Heaps: Binary heaps are binary trees that maintain a specific order property, such as the min-heap or max-heap property, which makes them ideal for implementing priority queues and efficient sorting algorithms like heapsort.
Balanced Trees: Various balanced binary trees, like AVL trees and Red-Black trees, ensure that the tree remains balanced, providing O(log n) time complexity for operations and maintaining efficiency even in the worst case.
Overall, the binary tree's restricted structure, along with its adaptability to various forms and algorithms, makes it a central topic in the study of data structures.
Types of Binary Trees
- Full Binary Tree: Every node has either 0 or 2 children.
- Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.
- Perfect Binary Tree: All internal nodes have exactly two children, and all leaf nodes are at the same level.
- Balanced Binary Tree: The height of the left and right subtrees of any node differ by at most one.
Implementation of Binary Tree
Binary trees can be implemented using linked lists. This method offers flexibility and is well-suited for trees that frequently change in size or structure. Linked lists allow dynamic memory allocation, making them ideal for trees where the number of nodes is not known in advance or changes frequently.
Creation of Binary Tree using Linked List
To create a binary tree using linked lists in C++, we define a class that includes a nested node class for representing individual nodes and the tree itself.
#include <iostream>
using namespace std;
class BinaryTreeLinkedList {
private:
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
~Node() {
delete left;
delete right;
}
};
Node* root;
public:
BinaryTreeLinkedList() : root(nullptr) {}
~BinaryTreeLinkedList() {
delete root;
}
};
Attributes Explanation
-
Node: A nested struct representing each node of the tree, containing:-
data: The value stored in the node. -
left: Pointer to the left child. -
right: Pointer to the right child.
-
-
root: Pointer to the root node of the tree.
Constructor Explanation
-
Node(int val): Initializes a node with a given value, settingleftandrighttonullptr. -
BinaryTreeLinkedList(): Initializes the tree withrootset tonullptr, indicating an empty tree. -
~Node(): Recursively deletes the node and its children to prevent memory leaks. -
~BinaryTreeLinkedList(): Deletes the root node, which in turn deletes the entire tree through the recursive destructor ofNode.
This setup provides the foundational framework for a binary tree using linked list implementations. The constructors ensure the tree is properly initialized and ready for further operations like insertion, deletion, and traversal.
Building Binary Tree
Building a binary tree involves creating nodes and connecting them in a hierarchical manner, ensuring each node has at most two children. The process can be dynamic, where elements are added one by one based on certain conditions or inputs. This allows for a flexible and interactive way of constructing the tree, especially when the structure is not known beforehand.
Inserting Elements One by One (Manually Making a Tree)
One way to build a binary tree is to insert elements one by one. During this process, the user specifies the value of each node. If a node should not have a left or right child, the user inputs -1 to indicate that the position is empty.
Here is a C++ function to build a binary tree interactively by inserting elements:
private:
Node* buildBinaryTree(Node* root) {
int value;
cin >> value;
if (value == -1) {
return nullptr;
}
root = new Node(value);
root->left = buildBinaryTree(root->left);
root->right = buildBinaryTree(root->right);
return root;
}
public:
void buildTree() {
root = buildBinaryTree(root);
}
By using these functions, you can construct a binary tree dynamically, allowing for user input at each step to determine the structure of the tree. The buildBinaryTree function is private, as it is a helper function that should only be called internally by the class. The buildTree function is public, providing an interface for initiating the tree-building process.
Inserting Element Using Array (Level Order Insertion)
Another way to build a binary tree is by using an array for level order insertion. This method is useful when we have a complete binary tree, where all levels are fully filled except possibly for the last level. The array representation simplifies the process, mapping array indices to tree positions.
Here is a C++ function to insert elements in level order using an array:
private:
Node* insertLevelOrder(vector<int> &array, int index) {
Node *root = nullptr;
if (index < array.size()) {
root = new Node(array[index]);
root->left = insertLevelOrder(array, 2 * index + 1);
root->right = insertLevelOrder(array, 2 * index + 2);
}
return root;
}
public:
void buildTreeFromArray(vector<int> &array) {
root = insertLevelOrder(array, 0);
}
Using this approach, the insertLevelOrder function recursively constructs the binary tree from the array. The buildTreeFromArray function is a public interface that initiates the tree-building process by calling insertLevelOrder with the initial index set to 0. This method ensures the tree is built in level order, making it well-suited for complete binary trees.
Tree Traversal
Tree traversal is the process of visiting all the nodes of a tree in a systematic way. There are three main traversal methods: preorder, inorder, and postorder. Each method defines a specific order in which nodes are visited, allowing us to perform different operations at each node.
Preorder Traversal
private:
void preorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
public:
void preorder() {
preorderTraversal(root);
}
Inorder Traversal
private:
void inorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
public:
void inorder() {
inorderTraversal(root);
}
Postorder Traversal
private:
void postorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
public:
void postorder() {
postorderTraversal(root);
}
Level Order Traversal
public:
void levelOrder() {
if (root == nullptr) {
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
cout << current->data << " ";
if (current->left != nullptr) {
q.push(current->left);
}
if (current->right != nullptr) {
q.push(current->right);
}
}
}
These traversal methods allow you to explore the nodes of the tree in different orders, performing various operations as needed. Each traversal method has its own applications and is useful for solving different types of problems.
Operations on Trees
Trees offer a variety of operations that allow us to explore and manipulate their structure. Here are some common operations along with brief explanations and code snippets:
Height of the Tree
The height of a tree is the length of the longest path from the root node to a leaf node. It represents the maximum number of edges in any path from the root to a leaf.
public:
int heightOfTree() {
return calculateHeight(root);
}
private:
int calculateHeight(Node* node) {
if (node == nullptr) {
return -1; // Height of an empty tree is -1
}
int leftHeight = calculateHeight(node->left);
int rightHeight = calculateHeight(node->right);
return 1 + max(leftHeight, rightHeight);
}
Height of the Given Node
The height of a given node in a tree is the length of the longest path from that node to a leaf node.
public:
int heightOfNode(Node* node) {
if (node == nullptr) {
return -1; // Height of a null node is -1
}
return calculateHeight(node);
}
private:
int calculateHeight(Node* node) {
if (node == nullptr) {
return -1;
}
int leftHeight = calculateHeight(node->left);
int rightHeight = calculateHeight(node->right);
return 1 + max(leftHeight, rightHeight);
}
Depth of the Tree
The depth of a tree is the length of the longest path from the root node to any leaf node.
public:
int depthOfTree() {
return calculateDepth(root);
}
private:
int calculateDepth(Node* node) {
if (node == nullptr) {
return 0; // Depth of an empty tree is 0
}
int leftDepth = calculateDepth(node->left);
int rightDepth = calculateDepth(node->right);
return 1 + max(leftDepth, rightDepth);
}
Depth of the Given Node
The depth of a given node in a tree is the length of the path from the root node to that node.
public:
int depthOfNode(Node* node) {
return calculateDepth(root, node, 0);
}
private:
int calculateDepth(Node* currentNode, Node* targetNode, int depth) {
if (currentNode == nullptr) {
return -1; // Node not found
}
if (currentNode == targetNode) {
return depth; // Node found, return depth
}
// Recur on left and right subtrees
int leftDepth = calculateDepth(currentNode->left, targetNode, depth + 1);
if (leftDepth != -1) {
return leftDepth;
}
return calculateDepth(currentNode->right, targetNode, depth + 1);
}
These operations allow us to gain insights into the structure of a tree, such as its height and depth, and to navigate to specific nodes within the tree. They are essential for various tree-based algorithms and analyses.
Full Code Implementation of Binary Tree
Binary trees can be implemented using linked lists, offering flexibility and dynamic memory allocation. Below is the full C++ implementation of a binary tree, including the necessary functions for building the tree, performing preorder traversal, and calculating various properties such as height and depth.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class BinaryTree {
private:
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
~Node() {
delete left;
delete right;
}
};
Node* root;
public:
BinaryTree() : root(nullptr) {}
~BinaryTree() {
delete root;
}
void buildTree() {
root = buildBinaryTree(root);
}
void buildTreeFromArray(vector<int>& array) {
root = insertLevelOrder(array, 0);
}
void preorder() {
preorderTraversal(root);
}
int heightOfTree() {
return calculateHeight(root);
}
int depthOfTree() {
return calculateDepth(root);
}
int depthOfNode(Node* node) {
return calculateDepth(root, node, 0);
}
private:
Node* buildBinaryTree(Node* root) {
int value;
cin >> value;
if (value == -1) {
return nullptr;
}
root = new Node(value);
root->left = buildBinaryTree(root->left);
root->right = buildBinaryTree(root->right);
return root;
}
Node* insertLevelOrder(vector<int>& array, int index) {
Node* root = nullptr;
if (index < array.size()) {
root = new Node(array[index]);
root->left = insertLevelOrder(array, 2 * index + 1);
root->right = insertLevelOrder(array, 2 * index + 2);
}
return root;
}
void preorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int calculateHeight(Node* node) {
if (node == nullptr) {
return -1; // Height of an empty tree is -1
}
int leftHeight = calculateHeight(node->left);
int rightHeight = calculateHeight(node->right);
return 1 + max(leftHeight, rightHeight);
}
int calculateDepth(Node* currentNode, Node* targetNode, int depth) {
if (currentNode == nullptr) {
return -1; // Node not found
}
if (currentNode == targetNode) {
return depth; // Node found, return depth
}
// Recur on left and right subtrees
int leftDepth = calculateDepth(currentNode->left, targetNode, depth + 1);
if (leftDepth != -1) {
return leftDepth;
}
return calculateDepth(currentNode->right, targetNode, depth + 1);
}
int calculateDepth(Node* node) {
if (node == nullptr) {
return 0; // Depth of an empty tree is 0
}
int leftDepth = calculateDepth(node->left);
int rightDepth = calculateDepth(node->right);
return 1 + max(leftDepth, rightDepth);
}
};
int main() {
BinaryTree tree;
cout << "Enter the elements of the binary tree (enter -1 for empty nodes):" << endl;
tree.buildTree();
cout << "Preorder Traversal: ";
tree.preorder();
cout << endl;
cout << "Height of the tree: " << tree.heightOfTree() << endl;
cout << "Depth of the tree: " << tree.depthOfTree() << endl;
// Example of calculating depth of a node (assuming node exists)
// Node* targetNode = tree.findNode(5);
// cout << "Depth of the node with value 5: " << tree.depthOfNode(targetNode) << endl;
return 0;
}
This code implements a binary tree using a linked list structure, allowing for dynamic creation and traversal of the tree. It includes functions for building the tree interactively or from an array, performing preorder traversal, and calculating the height and depth of the tree. You can customize and extend this code to include additional functionality as needed.
Top comments (0)