Welcome to Day 18 of my 100 Days of DSA challenge! Today, I solved five problems focused on basics of binary trees. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!
Before we jump to the questions let’s see what binary trees actually are.
A binary tree is a type of data structure where each node has at most two children, typically referred to as the left and right child. It's used to organize data in a hierarchical way.
A complete binary tree is a special kind of binary tree where every level, except possibly the last, is completely filled, and all nodes are as far left as possible. This ensures that the tree is balanced and has minimal depth.
Let’s solve the basic questions on binary trees.
1. Implement a binary tree with insertion and traversal (inorder, preorder, postorder).
First, create a Node class with attributes for data and left/right children. Implement an insert method to insert nodes in the tree (e.g., in a binary search tree, insert nodes based on value). For the traversals, use recursive methods:
Inorder: Left subtree, root, right subtree.
Preorder: Root, left subtree, right subtree.
Postorder: Left subtree, right subtree, root.
// to make a binary tree
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* left;
Node* right;
Node(int data){
this->data=data;
this->left=NULL;
this->right=NULL;
}
};
void inorderTraversal(Node* root){
if(root!=NULL){
inorderTraversal(root->left);
cout<<"-"<<root->data;
inorderTraversal(root->right);
}
}
void postorderTraversal(Node* root){
if(root!=NULL){
postorderTraversal(root->left);
postorderTraversal(root->right);
cout<<"-"<<root->data;
}
}
void preorderTraversal(Node* root){
if(root!=NULL){
cout<<"-"<<root->data;
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
int main(){
// Creating a binary tree
Node* root = new Node(10);
Node* one = new Node(20);
Node* two = new Node(30);
Node* three = new Node(40);
Node* four = new Node(50);
Node* five = new Node(60);
Node* six = new Node(70);
root->left = two;
root->right = one;
two->left = three;
two->right = four;
one->left = five;
one->right = six;
cout<<"The tree has been created."<<endl;
cout<<"Inorder traversal:"<<endl;
inorderTraversal(root);
cout<<endl;
cout<<"Preorder traversal:"<<endl;
preorderTraversal(root);
cout<<endl;
cout<<"Postorder traversal:"<<endl;
postorderTraversal(root);
}
2. Solve the "find the height of a binary tree" problem.
To find the height, create a recursive function that returns 0 if a node is None. For each node, calculate the height of its left and right subtrees and return the maximum of these heights plus one.
// To find the height of a binary tree
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* left;
Node* right;
Node(int data){
this->data=data;
this->left=NULL;
this->right=NULL;
}
};
int height(Node* root){
if(root==NULL){
return 0;
}
else{
int leftHeight=height(root->left);
int rightHeight=height(root->right);
return max(leftHeight,rightHeight)+1;
}
}
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);
cout<<"Height of the tree is:"<<height(root)<<endl;
}
3. Solve the "check if two binary trees are identical" problem.
Compare the two trees by checking if their roots have the same data. Then, recursively check if the left and right subtrees of both trees are identical.
// To check if two trees are identical
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* left;
Node* right;
Node(int data){
this->data=data;
this->left=NULL;
this->right=NULL;
}
};
bool identicalTrees(Node* root1, Node* root2){
if(root1 == NULL && root2==NULL){
return true;
}
if (root1 == NULL || root2 == NULL){
return false;
}
if(root1->data == root2->data && identicalTrees(root1->left, root2->left) && root1->right, root2->right){
return true;
}
else{
return false;
}
}
int main(){
Node* root1 = new Node(1);
root1->left = new Node(2);
root1->right = new Node(3);
root1->left->left = new Node(4);
root1->left->right = new Node(5);
// Create second binary tree
Node* root2 = new Node(1);
root2->left = new Node(2);
root2->right = new Node(3);
root2->left->left = new Node(4);
root2->left->right = new Node(5);
// Check if trees are identical
if (identicalTrees(root1, root2))
cout << "The trees are identical." << endl;
else
cout << "The trees are not identical." << endl;
}
4. Solve the "diameter of a binary tree" problem.
The diameter of a binary tree is the longest path between any two nodes. To find it, use a recursive function that computes the height of each subtree and tracks the maximum diameter by checking the sum of left and right subtree heights at each node.
// To find the diameter of binary trees
#include<iostream>
#include<algorithm>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int diameterOfBinaryTree(Node* root, int& diameter) {
if (root == NULL) {
return 0;
}
int leftHeight = diameterOfBinaryTree(root->left, diameter);
int rightHeight = diameterOfBinaryTree(root->right, diameter);
diameter = max(diameter, leftHeight + rightHeight);
return max(leftHeight, rightHeight) + 1;
}
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);
int diameter = 0;
diameterOfBinaryTree(root, diameter);
cout << "Diameter of the binary tree is: " << diameter << endl;
return 0;
}
5. Solve the "level-order traversal of a binary tree" problem.
For level-order traversal,also known as BFS, use a queue (FIFO) data structure. Start by enqueuing the root node, then dequeue nodes one by one, enqueueing their left and right children, and continue until the queue is empty, processing nodes level by level.
// To do the level order traversal also knowon as breadth first search of a tree
#include<iostream>
#include<queue>
using namespace std;
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* left;
Node* right;
Node(int data){
this->data=data;
this->left=NULL;
this->right=NULL;
}
};
void levelOrderTraversal(Node* root){
if(root==NULL) return;
queue<Node*>queue;
queue.push(root);
while(!queue.empty()){
Node* current = queue.front();
queue.pop();
cout<<current->data<<" "; // visiting the current node
if(current->left!=NULL) queue.push(current->left);
if(current->right!=NULL) queue.push(current->right);
}
}
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);
cout << "Level-order traversal of the binary tree: ";
levelOrderTraversal(root);
cout << endl;
}
This is all for today! See ya tomorrow :D