Table of contents
- Q1. Solve the "check if a binary tree is balanced" problem.
- Q2. Solve the "find the lowest common ancestor of two nodes in a binary tree" problem.
- Q3. Solve the "convert a binary tree to its mirror" problem.
- Q4. Solve the "zigzag level order traversal of a binary tree" problem.
- Q5. Solve the "flatten a binary tree to a linked list" problem.
Today, I explored advanced concepts in binary trees by solving problems that required deeper insights and creative solutions. I began with checking if a binary tree is balanced, ensuring the height difference between subtrees met the criteria. Then, I solved the "lowest common ancestor of two nodes" problem to find the shared ancestor in the tree structure. Next, I implemented a solution to convert a binary tree to its mirror and tackled the "zigzag level order traversal" problem for an alternate traversal approach. Finally, I solved the "flatten a binary tree to a linked list" problem, transforming tree structures into sequential forms.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Solve the "check if a binary tree is balanced" problem.
#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
// 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){
// Base case: If the node is NULL, return height as 1
if(root == NULL){
return 1;
}
// Recursively calculate the height of the left and right subtrees
int left_height = height_of_tree(root->left);
int right_height = height_of_tree(root->right);
// Return the maximum height of the left and right subtrees + 1 (for the current node)
return 1 + max(left_height, right_height);
}
// Function to calculate the height and check balance of the tree
int cal_height(Node* root){
// Base case: If the node is NULL, return height as 0
if(root == NULL){
return 0;
}
// Recursively calculate the height of the left subtree
int left_height = cal_height(root->left);
// If left subtree is unbalanced (i.e., height is -1), return -1 to indicate imbalance
if(left_height == -1){
return -1;
}
// Recursively calculate the height of the right subtree
int right_height = cal_height(root->right);
// If right subtree is unbalanced, return -1 to indicate imbalance
if(right_height == -1){
return -1;
}
// Check if the current node is balanced by comparing the heights of the left and right subtrees
if(abs(left_height - right_height) > 1){
return -1; // Tree is unbalanced
}
// Return the height of the current node
return 1 + max(left_height, right_height);
}
// Function to check if the tree is balanced
bool isBalanced(Node* root){
// A balanced tree will have no -1 height return value
return cal_height(root) != -1;
}
int main()
{
// Creating 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
// Check if the tree is balanced
if (!isBalanced(root)){
cout << "The tree is not balanced";
} else {
cout << "The tree is balanced";
}
return 0;
}
A binary tree is considered balanced if the height difference between its left and right subtrees at every node does not exceed one. The isBalanced function determines balance by calling cal_height, which calculates the height of the tree while simultaneously checking balance. If any subtree is unbalanced (i.e., the height difference is greater than one), cal_height returns -1, propagating the imbalance upwards. Otherwise, it returns the height of the current subtree. The main function constructs a binary tree, then uses isBalanced to evaluate its balance and outputs whether the tree is balanced or not.
Q2. Solve the "find the lowest common ancestor of two nodes in 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 find the Lowest Common Ancestor (LCA) of two nodes
Node* find_LCA(Node* root, Node* a, Node* b) {
// Base case: if root is NULL or root is one of the nodes (a or b), return root
if (root == NULL || root == a || root == b) {
return root;
}
// Recur for the left and right subtrees
Node* left = find_LCA(root->left, a, b);
Node* right = find_LCA(root->right, a, b);
// If both left and right are not NULL, then root is the LCA of a and b
if (left != NULL && right != NULL) {
return root;
}
// If left is NULL, return the right subtree (LCA is in the right subtree)
if (left == NULL) {
return right;
}
// If right is NULL, return the left subtree (LCA is in the left subtree)
return left;
}
// Helper function to find a node with a given value in the tree
Node* findNode(Node* root, int value) {
// Base case: if root is NULL, return NULL
if (root == NULL) {
return NULL;
}
// If the current node contains the value, return the node
if (root->data == value) {
return root;
}
// Recursively search for the node in the left subtree
Node* leftSearch = findNode(root->left, value);
if (leftSearch != NULL) {
return leftSearch;
}
// If not found in the left, recursively search in the right subtree
return findNode(root->right, value);
}
int main() {
// Creating 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
int a, b; // Variables to store the values of the nodes to find LCA of
cout << "Enter value of first element: ";
cin >> a;
cout << "Enter value of second element: ";
cin >> b;
// Find the nodes with values a and b
Node* loc_a = findNode(root, a);
Node* loc_b = findNode(root, b);
// Find the LCA of the two nodes
Node* lca = find_LCA(root, loc_a, loc_b);
// If LCA is NULL, print that no LCA exists
if (lca == NULL) {
cout << "No lowest common ancestor exists" << endl;
} else {
// If LCA is found, print the LCA's data
cout << "The lowest common ancestor of the two nodes is: " << lca->data << endl;
}
return 0;
}
The code implements a solution to find the Lowest Common Ancestor (LCA) of two nodes in a binary tree. The find_LCA function identifies the LCA by recursively checking the left and right subtrees of a given root. If the root matches either of the nodes or both nodes lie in different subtrees of the root, the root is the LCA. If both nodes are in the same subtree, the recursion continues in that direction. The findNode function locates a node with a specific value in the tree, facilitating LCA computation. In the main function, the binary tree is created, and the user provides two node values. The program locates these nodes, calculates their LCA using find_LCA, and prints the result. If one or both nodes do not exist, it indicates no LCA.
Q3. Solve the "convert a binary tree to its mirror" 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 convert the binary tree to its mirror
void convert_to_mirror(Node* root) {
// Base case: If the root is NULL, return
if (root) {
// Recursively mirror the left and right subtrees
convert_to_mirror(root->left);
convert_to_mirror(root->right);
// Swap the left and right child pointers to create the mirror
Node* temp = root->left;
root->left = root->right;
root->right = temp;
}
return;
}
// Function to perform inorder traversal of the binary tree
void inorder_traversal(struct Node* root) {
// Base case: If the node is NULL, return
if (root == NULL) {
return;
}
// Traverse the left subtree
inorder_traversal(root->left);
// Print the data of the node
cout << root->data << " ";
// Traverse the right subtree
inorder_traversal(root->right);
}
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
// Perform inorder traversal before converting to mirror
cout << "Inorder traversal before mirror: ";
inorder_traversal(root);
cout << endl;
// Convert the tree to its mirror
convert_to_mirror(root);
// Perform inorder traversal after converting to mirror
cout << "Inorder traversal after mirror: ";
inorder_traversal(root);
return 0;
}
This code demonstrates how to convert a binary tree into its mirror and perform inorder traversal of the tree before and after the conversion. It defines a Node structure with pointers to the left and right children, as well as a constructor to initialize the node with a given value. The convert_to_mirror function recursively swaps the left and right subtrees of each node, effectively creating the mirror image of the tree. The inorder_traversal function prints the nodes of the tree in inorder (left, root, right) sequence. In the main function, a binary tree is constructed, and the inorder traversal is displayed before and after calling the convert_to_mirror function. The output shows how the tree is mirrored by the changes in the inorder traversal result.
Q4. Solve the "zigzag level order traversal of a binary tree" problem.
#include <iostream>
using namespace std;
#include <queue>
#include <vector>
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 given 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 Zigzag level order traversal of the binary tree
vector<vector<int>> zigzag_traversal(Node* root){
vector<vector<int>> result; // To store the final result of zigzag traversal
if(root == NULL){ // If the tree is empty, return an empty result
return result;
}
queue<Node*> q; // Queue to perform level order traversal
q.push(root); // Push the root node to the queue
bool flag = true; // Flag to alternate the direction of traversal at each level
// Perform level order traversal
while(!q.empty()){
int size = q.size(); // Get the number of nodes at the current level
vector<int> row(size); // Vector to store nodes of the current level
// Traverse all nodes at the current level
for(int i = 0; i < size; i++){
Node* node = q.front(); // Get the front node in the queue
q.pop(); // Remove the node from the queue
// Determine the index for insertion based on the direction of traversal
int index = (flag) ? i : (size - 1 - i); // Alternate direction using the flag
row[index] = node->data; // Insert the node's data at the appropriate index in the row
// Push left and right children of the current node to the queue for the next level
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
flag = !flag; // Toggle the flag to alternate direction for the next level
result.push_back(row); // Add the current level to the result
}
return result; // Return the final result of zigzag traversal
}
int main()
{
// Constructing 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
// Get the zigzag traversal result
vector<vector<int>> result = zigzag_traversal(root);
// Display the zigzag level order traversal
cout << "Zigzag Level Order Traversal: " << endl;
for (const auto& level : result) {
for (int val : level) {
cout << val << " "; // Print each node value in the current level
}
cout << endl; // Move to the next level
}
return 0;
}
This code implements Zigzag level-order traversal of a binary tree. It defines a Node structure to represent the binary tree nodes, with left and right child pointers. The zigzag_traversal function performs level-order traversal using a queue, but alternates the direction of traversal at each level. It uses a flag (flag) to decide whether to traverse the level from left to right or right to left. For each level, the function computes the appropriate index for each node based on the direction of traversal and stores the node data in a vector (row). The nodes are added to the queue for the next level, and after processing a level, the flag is toggled to change the direction for the next level. The final result, a 2D vector, contains the nodes at each level in the required zigzag order. The main function constructs a binary tree, calls the zigzag_traversal function, and then prints the result.
Q5. Solve the "flatten a binary tree to a linked list" 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
}
};
// A global pointer to keep track of the previous node during flattening
Node* prev_node = NULL;
// Function to flatten the binary tree to a linked list
void flatten_to_LL(Node* root) {
// Base case: if the root is NULL, return
if (root == NULL) {
return;
}
// Recur for the right subtree first (right child becomes the next node in the linked list)
flatten_to_LL(root->right);
// Recur for the left subtree after the right child (left child becomes the previous node)
flatten_to_LL(root->left);
// Link the current node's right child to the previously visited node
root->right = prev_node;
// Set the current node's left child to NULL (as it's now a linked list)
root->left = NULL;
// Move the previous node pointer to the current node
prev_node = root;
}
// Function to perform inorder traversal of the binary tree
void inorder_traversal(Node* root) {
// Base case: if the node is NULL, return
if (root == NULL) {
return;
}
// Traverse the left subtree
inorder_traversal(root->left);
// Print the data of the node
cout << root->data << " ";
// Traverse the right subtree
inorder_traversal(root->right);
}
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
// Display the tree before flattening
cout << "Tree before flattening (inorder traversal): ";
inorder_traversal(root);
cout << endl;
// Flatten the tree into a linked list
flatten_to_LL(root);
// Display the flattened tree as a linked list
cout << "Flattened Tree as Linked List: ";
Node* curr = root;
while (curr != NULL) {
cout << curr->data << " "; // Print each node's data
curr = curr->right; // Move to the next node in the linked list
}
cout << endl;
return 0;
}
This code flattens a binary tree into a singly linked list following a specific order: the right child of each node becomes the next node in the list, and the left child of each node is set to NULL. The Node structure represents the binary tree with data, left, and right pointers. The flatten_to_LL function recursively flattens the tree. It first processes the right subtree, then the left subtree, linking the current node's right pointer to the previously processed node (prev_node) and setting the left pointer to NULL. The prev_node pointer keeps track of the last processed node. The inorder_traversal function is used to display the tree before flattening. In the main function, a sample binary tree is created, and the tree is displayed using inorder traversal before and after flattening, showing the flattened tree as a linked list.
Today's practice deepened my understanding of binary trees and their versatility in solving complex problems. From balancing checks and ancestor searches to structural transformations and zigzag traversals, I gained valuable experience in advanced binary tree operations. These exercises have enhanced my skills and prepared me for more intricate challenges in tree algorithms. Excited to continue building on this knowledge in the upcoming days!