Table of contents
- Q1. Implement a binary tree with insertion and traversal (inorder, preorder, postorder).
- Q2. Solve the "find the height of a binary tree" problem.
- Q3. Solve the "check if two binary trees are identical" problem.
- Q4. Solve the "diameter of a binary tree" problem.
- Q5. Solve the "level-order traversal of a binary tree" problem.
Today, I delved into the fundamentals of binary trees, implementing a binary tree with insertion and the three primary traversal methods: inorder, preorder, and postorder. I then tackled foundational problems, including finding the height of a binary tree and checking if two binary trees are identical. Moving forward, I solved the "diameter of a binary tree" problem to determine the longest path between two nodes. Finally, I implemented level-order traversal to explore binary trees layer by layer. These exercises built a strong foundation for understanding and working with binary trees.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Implement a binary tree with insertion and traversal (inorder, preorder, postorder).
#include <iostream>
using namespace std;
struct Node{
int data; //Data of the node
struct Node* left; //Pointer to left child
struct Node* right; //Pointer to right child
Node(int val){ //Ctor to initialize a node
data=val;
right=NULL;
left=NULL;
}
};
void insertion(struct Node* root, int data){
}
void preorder_traversal(struct Node* root){
if(root == NULL){ //Base condition
return;
}
cout<<root->data<<" "; //root
preorder_traversal(root->right); //right
preorder_traversal(root->left); //left
}
void inorder_traversal(struct Node* root){
if(root==NULL){
return;
}
inorder_traversal(root->left);
cout<<root->data<<" ";
inorder_traversal(root->right);
}
void postorder_traversal(struct Node* root){
if(root==NULL){
return;
}
postorder_traversal(root->left);
postorder_traversal(root->right);
cout<<root->data<<" ";
}
int main()
{
struct 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);
cout<<"Preorder Traversal: ";
preorder_traversal(root);
cout<<endl;
cout<<"Inorder Traversal: ";
inorder_traversal(root);
cout<<endl;
cout<<"Postorder Traversal: ";
postorder_traversal(root);
cout<<endl;
return 0;
}
This code defines a binary tree structure using the Node struct, where each node contains data and pointers to its left and right children. The main function manually constructs a binary tree with the root node as 1, its children as 2 and 3, and their respective children as 4, 5, 6, 7. Three traversal methods are implemented: preorder (visit root, right, left), inorder (visit left, root, right), and postorder (visit left, right, root). These functions are recursive and process the tree in their respective orders. The tree structure and traversal outputs showcase the logical order of node visits for each traversal type.
Q2. Solve the "find the height of a binary tree" problem.
#include <iostream>
using namespace std;
// Definition of a binary tree node
struct Node {
int data; // Data of the node
struct Node* left; // Pointer to left child
struct Node* right; // Pointer to right child
// Constructor to initialize a node with a value
Node(int val) {
data = val; // Set the data for the node
right = NULL; // Initialize right child as NULL
left = NULL; // Initialize left child as NULL
}
};
// Function to calculate the height of a binary tree
int height_of_tree(Node* root) {
// If the tree is empty, return height as 0
if (root == NULL) {
return 0;
}
// Recursively find the height of left and right subtrees
int left_height = height_of_tree(root->left);
int right_height = height_of_tree(root->right);
// Return the height of the current tree, which is 1 plus the maximum of the heights of left and right subtrees
return 1 + max(left_height, right_height);
}
int main() {
// Create a binary tree
struct Node* root = new Node(1); // Root node
root->left = new Node(2); // Left child of root
root->right = new Node(3); // Right child of root
root->left->left = new Node(4); // Left child of left child
root->left->right = new Node(5); // Right child of left child
root->right->left = new Node(6); // Left child of right child
root->right->right = new Node(7); // Right child of right child
// Call the function to find the height of the tree and display the result
cout << "Height of the tree is: " << height_of_tree(root);
return 0;
}
This code defines a binary tree structure using a Node struct, where each node contains data and pointers to its left and right children. The height_of_tree function calculates the height of the tree recursively by determining the height of the left and right subtrees of each node and taking the maximum of the two, adding 1 to include the current node. The main function constructs a binary tree with a root node of 1, its children 2 and 3, and their respective children 4, 5, 6, and 7. Finally, the height of the tree is computed using height_of_tree, and the result is printed. The height is the number of edges in the longest path from the root to a leaf node.
Q3. Solve the "check if two binary trees are identical" problem.
#include <iostream>
using namespace std;
// Definition of a binary tree node
struct Node {
int data; // Data of the node
struct Node* left; // Pointer to left child
struct Node* right; // Pointer to right child
// Constructor to initialize a node with a value
Node(int val) {
data = val; // Set the data for the node
right = NULL; // Initialize right child as NULL
left = NULL; // Initialize left child as NULL
}
};
// Function to check if two binary trees are identical
int check_identical(Node* root1, Node* root2) {
// If both trees are empty, they are identical
if (root1 == NULL && root2 == NULL) {
return 1;
}
// If one tree is empty and the other is not, they are not identical
if (root1 == NULL || root2 == NULL) {
return 0;
}
// If the data at the current node is different, the trees are not identical
if (root1->data != root2->data) {
return 0;
}
// Recursively check left and right subtrees
return check_identical(root1->left, root2->left) && check_identical(root1->right, root2->right);
}
int main() {
// Create the first binary tree (root1)
struct Node* root1 = new Node(1); // Root node
root1->left = new Node(2); // Left child of root
root1->right = new Node(3); // Right child of root
// Create the second binary tree (root2)
struct Node* root2 = new Node(1); // Root node
root2->left = new Node(2); // Left child of root
root2->right = new Node(5); // Right child of root
// Create the third binary tree (root3)
struct Node* root3 = new Node(1); // Root node
root3->left = new Node(2); // Left child of root
root3->right = new Node(3); // Right child of root
// Check if root1 and root2 are identical
if (!check_identical(root1, root2)) {
cout << "The trees are not identical"; // If not identical
} else {
cout << "The trees are identical"; // If identical
}
cout << endl;
// Check if root1 and root3 are identical
if (!check_identical(root1, root3)) {
cout << "The trees are not identical"; // If not identical
} else {
cout << "The trees are identical"; // If identical
}
return 0;
}
This code defines a binary tree structure and includes a function, check_identical, to determine whether two binary trees are identical. Two trees are considered identical if they have the same structure and corresponding nodes have the same values. The function recursively compares the root nodes of both trees and their left and right subtrees. In the main function, three binary trees (root1, root2, and root3) are created. The trees root1 and root3 are identical, while root1 and root2 differ in the value of one node. The program checks and prints whether root1 is identical to root2 and root1 to root3, outputting the respective results based on the comparisons.
Q4. Solve the "diameter of a binary tree" problem.
#include <iostream>
using namespace std;
// Definition of a binary tree node
struct Node {
int data; // Data of the node
struct Node* left; // Pointer to left child
struct Node* right; // Pointer to right child
// Constructor to initialize a node with a value
Node(int val) {
data = val; // Set the data for the node
right = NULL; // Initialize right child as NULL
left = NULL; // Initialize left child as NULL
}
};
// Function to find the diameter of a binary tree
int findDiameter(Node* root, int &diameter) {
// If the tree is empty, return 0
if (root == NULL) {
return 0;
}
// Recursively find the height of left and right subtrees
int left_height = findDiameter(root->left, diameter);
int right_height = findDiameter(root->right, diameter);
// Update the diameter by comparing with the sum of left and right subtree heights
diameter = max(diameter, left_height + right_height);
// Return the height of the current subtree
return 1 + max(left_height, right_height);
}
int main() {
// Create a binary tree
struct Node* root = new Node(1); // Root node
root->left = new Node(2); // Left child of root
root->right = new Node(3); // Right child of root
root->left->left = new Node(4); // Left child of left child
root->left->right = new Node(5); // Right child of left child
root->right->left = new Node(6); // Left child of right child
root->right->right = new Node(7); // Right child of right child
// Variable to store the diameter of the tree
int diameter = 0;
// Call the function to find the diameter
cout << "The diameter of the tree is " << findDiameter(root, diameter);
return 0;
}
This code calculates the diameter of a binary tree. The diameter is defined as the maximum number of nodes on any path between two leaf nodes, which is equivalent to the sum of the heights of the left and right subtrees of a node for the longest path. The function findDiameter recursively calculates the height of the left and right subtrees of each node while updating the diameter to the maximum of its current value and the sum of the left and right subtree heights. The main function constructs a binary tree, initializes a diameter variable to zero, and calls findDiameter to compute the diameter. The result is then displayed as the diameter of the tree.
Q5. Solve the "level-order traversal of a binary tree" problem.
#include <iostream>
using namespace std;
#include <queue>
// Definition of a binary tree node
struct Node {
int data; // Data of the node
struct Node* left; // Pointer to left child
struct Node* right; // Pointer to right child
// Constructor to initialize a node with a value
Node(int val) {
data = val; // Set the data for the node
right = NULL; // Initialize right child as NULL
left = NULL; // Initialize left child as NULL
}
};
// Function to perform level-order traversal of the binary tree
void level_order_traversal(Node* root) {
// If the tree is empty, return immediately
if (root == NULL) {
return;
}
// Create a queue to hold nodes at each level
queue<Node*> q;
q.push(root); // Push the root node into the queue
q.push(NULL); // Add a NULL marker to indicate the end of a level
// Process nodes level by level
while (!q.empty()) {
// Get the front node from the queue
Node* node = q.front();
q.pop(); // Remove the node from the queue
// If the node is not NULL, print the data and add its children to the queue
if (node != NULL) {
cout << node->data << " "; // Print the data of the node
// Push left child to the queue if it exists
if (node->left != NULL) {
q.push(node->left);
}
// Push right child to the queue if it exists
if (node->right != NULL) {
q.push(node->right);
}
}
// If the node is NULL, we reach the end of the current level
else if (!q.empty()) {
// Push a NULL marker to indicate the end of the next level
q.push(NULL);
}
}
}
int main() {
// Create a binary tree
struct Node* root = new Node(1); // Root node
root->left = new Node(2); // Left child of root
root->right = new Node(3); // Right child of root
root->left->left = new Node(4); // Left child of left child
root->left->right = new Node(5); // Right child of left child
root->right->left = new Node(6); // Left child of right child
root->right->right = new Node(7); // Right child of right child
// Call the function to perform level-order traversal and display the result
level_order_traversal(root);
return 0;
}
This code performs a level-order traversal of a binary tree using a queue. Level-order traversal visits all nodes at each level from left to right, starting from the root. The function level_order_traversal takes the root node as input and uses a queue to process nodes level by level. Initially, the root is added to the queue, followed by a NULL marker to signify the end of the first level. The function dequeues nodes one by one, prints their values, and enqueues their left and right children if they exist. When encountering a NULL, it marks the end of the current level, and if more nodes remain in the queue, another NULL is added to indicate the end of the next level. In the main function, a binary tree is constructed, and the traversal function is called to display the tree's nodes level by level.
Today's practice reinforced my knowledge of binary trees and their traversal techniques. From constructing and traversing trees to solving problems like calculating tree height and diameter, I gained a deeper understanding of their structure and utility. These exercises have prepared me to handle more complex tree-related problems in the future, and I am excited to explore advanced tree algorithms in the coming days!