What is Tree?
A tree is a hierarchical data structure consisting of nodes connected by edges. It is used to represent hierarchical relationships among elements. The structure resembles an inverted tree, with the root at the top and leaves at the bottom.
Key Terms:
- Root: The top node of the tree.
- Node: Each element in the tree.
- Edge: Connection between two nodes.
- Parent: The node which is a predecessor of a node is called parent of that node.
- Child: The node which is the immediate successor of a node.
- Leaf: A node with no children.
- Ancestor: Any predecessor nodes on the path of the root to the node are called ancestors of that node.
- Siblings: Children of the same parent.
- Level of Node: The count of levels on the path from the root node to that node.
- Degree of a Node: The total number of children of a node is called as degree of that node.
- Degree of Tree: The highest degree of a node among all nodes in the tree.
- Height: Max level at which a node exists.
- Depth: The length of the path from the root to a node.
Main Types of Trees:
1. Binary Tree
2. Binary Search Tree (BST)
3. AVL Tree
Binary Tree:
A tree where each node has at most two children, referred to as the left child and the right child.
Maximum number of nodes at a specific level (k):
2^k-1
Maximum number of nodes in a Tree:
(2^k)-1 Here, k = Max Level of Tree
Binary Tree Traversals:
Preorder Traversal (Current-Left-Right):
Visit the current node before visiting any nodes inside the left or right subtrees. Here the traversal is Current-Left-Right.
Output -> 8, 3, 9, 2, 4, 11, 6
Inorder Traversal (Left-Current-Right):
Visit the current node after visiting all nodes inside the left subtree but before visiting any node within the right subtree.
Output -> 9, 3, 2, 8, 11, 4, 6
Postorder Traversal (Left-Right-Current):
Visit the current node after visiting all the nodes of the left and right subtrees.
Output -> 9, 2, 3, 11, 6, 4, 8
Level Order Traversal:
Visit nodes level-by-level and left-to-right fashion at the same level. Here the traversal is level-wise.
Output -> 8, 3, 4, 9, 2, 11, 6
Binary Search Tree (BST):
A special type of binary tree in which left child's value is less than parent's value and right child's value is greater than parent's value.
#include <iostream> // Include the iostream library for input/output operations
#include <queue> // Include the queue library for using the queue data structure
using namespace std; // Use the standard namespace
// Class representing a node in the binary search tree (BST)
class TreeNode
{
int Data; // Data stored in the node
TreeNode* Left; // Pointer to the left child
TreeNode* Right; // Pointer to the right child
// Declare BST class as a friend to allow it to access private members of TreeNode
friend class BST;
};
// Class representing a binary search tree (BST)
class BST
{
private:
TreeNode* Root; // Pointer to the root node of the BST
// Helper function to insert a new node recursively
void insertRecursive(TreeNode*& currNode, TreeNode* newNode)
{
if (currNode == nullptr) // If current node is null
currNode = newNode; // Place the new node here
else if (newNode->Data < currNode->Data) // If new node's data is less than current node's data
insertRecursive(currNode->Left, newNode); // Recur on the left subtree
else // Otherwise
insertRecursive(currNode->Right, newNode); // Recur on the right subtree
}
// Helper function to perform in-order traversal recursively
void inOrderRecursive(TreeNode* currNode)
{
if (currNode != nullptr) // If current node is not null
{
inOrderRecursive(currNode->Left); // Recur on the left subtree
cout << currNode->Data << " "; // Print the data
inOrderRecursive(currNode->Right);// Recur on the right subtree
}
}
// Helper function to perform pre-order traversal recursively
void preOrderRecursive(TreeNode* currNode)
{
if (currNode != nullptr) // If current node is not null
{
cout << currNode->Data << " "; // Print the data
preOrderRecursive(currNode->Left); // Recur on the left subtree
preOrderRecursive(currNode->Right);// Recur on the right subtree
}
}
// Helper function to perform post-order traversal recursively
void postOrderRecursive(TreeNode* currNode)
{
if (currNode != nullptr) // If current node is not null
{
postOrderRecursive(currNode->Left); // Recur on the left subtree
postOrderRecursive(currNode->Right);// Recur on the right subtree
cout << currNode->Data << " "; // Print the data
}
}
// Helper function to perform level-order traversal using a queue
void levelorderPrintHelper(TreeNode* currNode)
{
if (currNode == nullptr) // If current node is null
return; // Exit the function
queue<TreeNode*> q; // Create a queue to hold nodes
q.push(currNode); // Push the current node to the queue
while (!q.empty()) // While the queue is not empty
{
int levelSize = q.size(); // Get the number of nodes at the current level
for (int i = 0; i < levelSize; ++i) // For each node at the current level
{
TreeNode* node = q.front(); // Get the front node from the queue
q.pop(); // Remove the front node from the queue
cout << node->Data << " "; // Print the node's data
if (node->Left) // If the left child exists
q.push(node->Left); // Push the left child to the queue
if (node->Right) // If the right child exists
q.push(node->Right); // Push the right child to the queue
}
cout << endl; // Print a new line after each level
}
}
// Helper function to search for a value recursively
bool searchRecursive(TreeNode* currNode, int Value)
{
if (currNode == nullptr) // If current node is null
return false; // Value not found
else if (currNode->Data == Value) // If current node's data matches the value
return true; // Value found
else if (Value < currNode->Data) // If the value is less than current node's data
return searchRecursive(currNode->Left, Value); // Recur on the left subtree
else // Otherwise
return searchRecursive(currNode->Right, Value);// Recur on the right subtree
}
// Helper function to count the number of nodes recursively
int countNodesRecursive(TreeNode* currNode)
{
if (currNode == nullptr) // If current node is null
return 0; // No nodes
return 1 + countNodesRecursive(currNode->Left) + countNodesRecursive(currNode->Right); // 1 for the current node + count of nodes in left and right subtrees
}
// Helper function to count the number of leaf nodes recursively
int leafCountRecursive(TreeNode* currNode)
{
if (currNode == nullptr) // If current node is null
return 0; // No leaf nodes
if (currNode->Left == nullptr && currNode->Right == nullptr) // If current node has no children
return 1; // Current node is a leaf
return leafCountRecursive(currNode->Left) + leafCountRecursive(currNode->Right); // Sum of leaf nodes in left and right subtrees
}
// Helper function to delete the entire tree
void DeleteTree(TreeNode* node)
{
if (node != nullptr) // If current node is not null
{
DeleteTree(node->Left); // Recur on the left subtree
DeleteTree(node->Right); // Recur on the right subtree
delete node; // Delete the current node
}
}
public:
// Constructor initializes the root to nullptr
BST()
{
Root = nullptr; // Initialize root to null
}
// Function to insert a new value into the BST
void Insert(int Value)
{
TreeNode* newNode = new TreeNode; // Create a new node
newNode->Data = Value; // Set the node's data
newNode->Left = newNode->Right = nullptr; // Initialize left and right children to null
insertRecursive(Root, newNode); // Insert the new node recursively
}
// Function to perform in-order traversal
void inOrder()
{
inOrderRecursive(Root); // Perform in-order traversal recursively starting from root
}
// Function to perform pre-order traversal
void preOrder()
{
preOrderRecursive(Root); // Perform pre-order traversal recursively starting from root
}
// Function to perform post-order traversal
void postOrder()
{
postOrderRecursive(Root); // Perform post-order traversal recursively starting from root
}
// Function to perform level-order traversal
void levelorderPrint()
{
levelorderPrintHelper(Root); // Perform level-order traversal starting from root
}
// Function to search for a value in the BST
void Search(int Value)
{
if (Root == nullptr) // If the tree is empty
cout << "TREE is Empty!" << endl; // Print message
else if (searchRecursive(Root, Value)) // If value is found
cout << "Value " << Value << " Found!" << endl; // Print message
else // If value is not found
cout << "Value " << Value << " not Found!" << endl; // Print message
}
// Function to count the number of nodes in the BST
int countNodes()
{
return countNodesRecursive(Root); // Count nodes recursively starting from root
}
// Function to count the number of leaf nodes in the BST
int leafCount()
{
return leafCountRecursive(Root); // Count leaf nodes recursively starting from root
}
// Function to find the minimum value in the BST
int Minimum()
{
if (Root == nullptr) // If the tree is empty
{
cout << "TREE is Empty!" << endl; // Print message
return -1; // Return -1 to indicate error
}
TreeNode* currNode = Root; // Start from root
while (currNode->Left != nullptr) // Traverse to the leftmost node
{
currNode = currNode->Left; // Move to the left child
}
return currNode->Data; // Return the data of the leftmost node
}
// Function to find the maximum value in the BST
int Maximum()
{
if (Root == nullptr) // If the tree is empty
{
cout << "TREE is Empty!" << endl; // Print message
return -1; // Return -1 to indicate error
}
TreeNode* currNode = Root; // Start from root
while (currNode->Right != nullptr) // Traverse to the rightmost node
{
currNode = currNode->Right; // Move to the right child
}
return currNode->Data; // Return the data of the rightmost node
}
// Function to remove a value from the BST
bool Remove(int Value)
{
TreeNode* currNode = Root, * Parent = nullptr; // Start from root and initialize parent to null
// Find the node to be deleted and its parent
while (currNode != nullptr && currNode->Data != Value)
{
Parent = currNode; // Update parent
if (Value < currNode->Data) // If value is less than current node's data
currNode = currNode->Left; // Move to the left child
else // Otherwise
currNode = currNode->Right; // Move to the right child
}
if (currNode == nullptr) // If the node to be deleted is not found
return false; // Return false
else
{
// If the node has two children
if (currNode->Left != nullptr && currNode->Right != nullptr)
{
TreeNode* l = currNode->Left, * parentLeft = currNode; // Find the rightmost node in the left subtree
while (l->Right != nullptr) // While right child exists
{
parentLeft = l; // Update parent
l = l->Right; // Move to the right child
}
currNode->Data = l->Data; // Copy the data from the rightmost node
currNode = l; // Update currNode to the rightmost node
Parent = parentLeft; // Update Parent to parentLeft
}
TreeNode* Child;
if (currNode->Left != nullptr) // If the left child exists
Child = currNode->Left; // Set Child to the left child
else // Otherwise
Child = currNode->Right; // Set Child to the right child
if (currNode == Root) // If the node to be deleted is the root
Root = Child; // Update Root to Child
else
{
if (currNode == Parent->Left) // If currNode is the left child of Parent
Parent->Left = Child; // Update Parent's left child to Child
else // Otherwise
Parent->Right = Child; // Update Parent's right child to Child
}
}
delete currNode; // Delete the node
currNode = nullptr; // Set currNode to null
return true; // Return true
}
// Function to sum the nodes in the BST recursively
void NodesSum(TreeNode* Curr, int& Sum)
{
if (Curr != nullptr) // If current node is not null
{
Sum += Curr->Data; // Add current node's data to Sum
NodesSum(Curr->Left, Sum); // Recur on the left subtree
NodesSum(Curr->Right, Sum); // Recur on the right subtree
}
}
// Function to calculate the maximum depth of the BST
int MaxDepth()
{
if (Root == nullptr) // If the tree is empty
return 0; // Return 0
queue<TreeNode*> q; // Create a queue to hold nodes
q.push(Root); // Push the root to the queue
int MaxLevel = 0; // Initialize MaxLevel to 0
while (!q.empty()) // While the queue is not empty
{
MaxLevel++; // Increment MaxLevel
int LevelSize = q.size(); // Get the number of nodes at the current level
for (int i = 0; i < LevelSize; i++) // For each node at the current level
{
TreeNode* temp = q.front(); // Get the front node from the queue
q.pop(); // Remove the front node from the queue
if (temp->Left) // If the left child exists
q.push(temp->Left); // Push the left child to the queue
if (temp->Right) // If the right child exists
q.push(temp->Right); // Push the right child to the queue
}
}
return MaxLevel; // Return the maximum depth
}
// Destructor to delete the entire tree
~BST()
{
DeleteTree(Root); // Delete the tree starting from root
}
};
AVL Tree:
A BST with height balanced factor. Every node in AVL should have either -1, 0, or +1 balancing factor. The difference between the heights of the left subtree and the right subtree for any node is known as the balance factor for the node.
Balance Factor = Height of Left Subtree - Height of Right Subtree
Ways to convert BST to AVL Tree:
#include <iostream> // Include the iostream library for input/output operations
using namespace std; // Use the standard namespace
// Class representing a node in the AVL tree
class TreeNode
{
int data; // Data stored in the node
TreeNode* left; // Pointer to the left child
TreeNode* right; // Pointer to the right child
int height; // Height of the node for balancing
// Constructor to initialize a new node with a given value
TreeNode(int value)
{
data = value; // Set the node's data
left = nullptr; // Initialize left child to null
right = nullptr; // Initialize right child to null
height = 1; // Initialize node's height to 1
}
// Declare AVLTree class as a friend to allow it to access private members of TreeNode
friend class AVLTree;
};
// Class representing an AVL tree
class AVLTree
{
TreeNode* root; // Pointer to the root node of the AVL tree
// Function to get the height of a node
int getHeight(TreeNode* node)
{
if (node == nullptr) // If the node is null
return 0; // Height is 0
return node->height; // Otherwise, return the node's height
}
// Function to get the balance factor of a node
int getBalanceFactor(TreeNode* node)
{
if (node == nullptr) // If the node is null
return 0; // Balance factor is 0
return getHeight(node->left) - getHeight(node->right); // Balance factor is the difference in height between left and right subtrees
}
// Function to perform left rotation
TreeNode* leftRotate(TreeNode* x)
{
TreeNode* temp1 = x->right; // Set temp1 to right child of x
TreeNode* temp2 = temp1->left; // Set temp2 to left child of temp1
temp1->left = x; // Make x the left child of temp1
x->right = temp2; // Make temp2 the right child of x
// Update heights of x and temp1
x->height = 1 + max(getHeight(x->left), getHeight(x->right));
temp1->height = 1 + max(getHeight(temp1->left), getHeight(temp1->right));
return temp1; // Return new root of the subtree
}
// Function to perform right rotation
TreeNode* rightRotate(TreeNode* y)
{
TreeNode* temp1 = y->left; // Set temp1 to left child of y
TreeNode* temp2 = temp1->right; // Set temp2 to right child of temp1
temp1->right = y; // Make y the right child of temp1
y->left = temp2; // Make temp2 the left child of y
// Update heights of y and temp1
y->height = 1 + max(getHeight(y->left), getHeight(y->right));
temp1->height = 1 + max(getHeight(temp1->left), getHeight(temp1->right));
return temp1; // Return new root of the subtree
}
// Function to insert a new value into the AVL tree
TreeNode* Insert(TreeNode* node, int data)
{
if (node == nullptr) // If current node is null
return new TreeNode(data); // Create a new node with the given data
if (data < node->data) // If data is less than current node's data
node->left = Insert(node->left, data); // Recur on the left subtree
else if (data > node->data) // If data is greater than current node's data
node->right = Insert(node->right, data); // Recur on the right subtree
else // If data is equal to current node's data
return node; // Return the current node (no duplicates allowed)
// Update height of the current node
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
// Get balance factor of the current node
int balance = getBalanceFactor(node);
// Left heavy case
if (balance > 1)
{
if (data < node->left->data) // Left-Left case
return rightRotate(node); // Perform right rotation
else // Left-Right case
{
node->left = leftRotate(node->left); // Perform left rotation on left child
return rightRotate(node); // Perform right rotation on the current node
}
}
// Right heavy case
if (balance < -1)
{
if (data > node->right->data) // Right-Right case
return leftRotate(node); // Perform left rotation
else // Right-Left case
{
node->right = rightRotate(node->right); // Perform right rotation on right child
return leftRotate(node); // Perform left rotation on the current node
}
}
return node; // Return the current node
}
public:
// Constructor initializes the root to nullptr
AVLTree()
{
root = nullptr; // Initialize root to null
}
// Function to insert a new value into the AVL tree
void insert(int value)
{
root = Insert(root, value); // Insert the new value starting from root
}
};
