winter camp 2

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Daily Assignment – 27rd Dec 2024
Student Name: Lakshay UID: 22BCS16259

Branch: CSE Section/Group: FL_604/A
Subject Name: WWC Date of Performance: Dec 27, 2024
Problem: 1
1. Aim: Binary Tree Inorder Traversal

2. Objective: Given the root of a binary tree, return the inorder traversal of its nodes' values.
3. Code:
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
using namespace std;
// Definition for a binary tree node.

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// Function to perform inorder traversal

void inorderTraversal(TreeNode* root, vector<int>& result) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left, result); // Visit left subtree result.push_back(root-
>val); // Visit root
inorderTraversal(root->right, result); // Visit right subtree
}
// Function to create a binary tree from input

TreeNode* createBinaryTree(const vector<string>& nodes) {
1
DEPARTMENT OF
if (nodes.empty() || nodes[0] == "null") {
return nullptr;
}
TreeNode* root = new

TreeNode(stoi(nodes[0])); queue<TreeNode*> q;
q.push(root);
int index = 1;
while (!q.empty() && index < nodes.size())

{ TreeNode* current = q.front();
q.pop();
// Create left child

if (index < nodes.size() && nodes[index] != "null") {
current->left = new TreeNode(stoi(nodes[index]));
q.push(current->left);
}
index++;
// Create right child

current->right = new TreeNode(stoi(nodes[index]));
q.push(current->right);
}
index++;
}
return root;
}
int main() { string input; cout << "Enter the binary tree nodes in level order (use 'null' for
empty nodes, space-separated): "; getline(cin, input);
// Split the input string into a

vector stringstream ss(input);
vector<string> nodes; string node;
while (ss >> node) {
nodes.push_back(node);
}
TreeNode* root = createBinaryTree(nodes); // Create the binary tree

vector<int> result; // Vector to store the inorder traversal result
2
DEPARTMENT OF
inorderTraversal(root, result); // Perform inorder traversal
// Output the result cout

<< "Inorder traversal: ";
for (int val : result) {
cout << val << " ";
}
cout << endl;
return 0;
}
4. Output:
Problem: 2
1. Aim: Binary Tree - Find Maximum Depth
2. Objective: A binary tree's maximum depth is the number of nodes along the longest path from the root
node down to the farthest leaf node.
3. Code:
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>

struct TreeNode {
int val;
TreeNode *left;
3
DEPARTMENT OF
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };
// Function to calculate the maximum depth of the binary tree

int calculateMaxDepth(TreeNode* root) {
return 0; // Base case: if the tree is empty, depth is 0
}
// Recursively find the depth of the left and right subtrees and add 1 for the root
return 1 + max(calculateMaxDepth(root->left), calculateMaxDepth(root->right)); }

TreeNode* buildBinaryTree(const vector<string>& nodes) {
return nullptr;
}
TreeNode* root = new TreeNode(stoi(nodes[0]));

queue<TreeNode*> q; q.push(root); int index
= 1;
while (!q.empty() && index < nodes.size()) {

TreeNode* current = q.front(); q.pop();

}
index++;

}
index++;
}
return root;
}
4
DEPARTMENT OF
int main() {
string input;
cout << "Enter the binary tree nodes in level order (use 'null' for empty nodes, space-separated): ";
getline(cin, input);
// Split the input string into a vector

stringstream ss(input);
}
TreeNode* root = buildBinaryTree(nodes); // Create the binary tree
int depth = calculateMaxDepth(root); // Calculate the maximum depth
// Output the result

cout << "Maximum depth of the binary tree: " << depth << endl;
return 0;
}
4. Output:
Problem: 3
1. Aim: Binary Tree Preorder Traversal

2. Objective: Given the root of a binary tree, return the preorder traversal of its nodes' values.
3. Code:
#include <iostream>
#include <vector>
5
DEPARTMENT OF
#include <queue>
#include <sstream>

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
// Function to perform preorder traversal

void performPreorderTraversal(TreeNode* root, vector<int>& result) {
return;
}
result.push_back(root->val); // Visit root performPreorderTraversal(root-
>left, result); // Visit left subtree performPreorderTraversal(root->right, result); //
Visit right subtree
}

TreeNode* createBinaryTreeFromInput(const vector<string>& nodes) {
return nullptr;
}

queue<TreeNode*> q; q.push(root);
int index = 1;


}
index++;
6
DEPARTMENT OF
}
index++;
}
return root;
}
int main() {
string input;

vector<string> nodes;
string node; while
(ss >> node) {
}
TreeNode* root = createBinaryTreeFromInput(nodes); // Create the binary tree
vector<int> result; // Vector to store the preorder traversal result
performPreorderTraversal(root, result); // Perform preorder traversal
// Output the result cout <<

"Preorder traversal: ";
for (int val : result) {
cout << val << " ";
}
cout << endl;
return 0;
}
4. Output:
7
DEPARTMENT OF
Problem: 4
1. Aim: Invert Binary Tree
2. Objective: Given the root of a binary tree, invert the tree, and return its root.
3. Code:
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
// Function to invert the binary tree
8
DEPARTMENT OF
TreeNode* invertBinaryTree(TreeNode* root) {
return nullptr; // Base case: if the tree is empty

}
// Swap the left and right children swap(root-
>left, root->right);
// Recursively invert the left and right subtrees invertBinaryTree(root->left);

invertBinaryTree(root->right); return root; // Return the root of the inverted tree

TreeNode* constructBinaryTree(const vector<string>& nodes) {
if (nodes.empty() || nodes[0] == "null") { return nullptr;

queue<TreeNode*> q; q.push(root); int index
= 1;


}
9
DEPARTMENT OF
index++;

}
index++;
}
return root;
}
// Function to perform level order traversal and print the tree

void printLevelOrder(TreeNode* root) { if (root ==
nullptr) { cout << "[]"; return;
queue<TreeNode*> q;
q.push(root); cout << "[";
while (!q.empty()) {
TreeNode* current = q.front();
q.pop(); if (current) {
cout << current->val << ",";
10
DEPARTMENT OF
} else { cout <<
"null,";
}
}
cout << "\b]"; // Remove the last comma
}
int main() {
string input;

TreeNode* root = constructBinaryTree(nodes); // Create the binary tree
root = invertBinaryTree(root); // Invert the binary tree
// Output the inverted tree cout

<< "Inverted binary tree: ";
printLevelOrder(root);
11
DEPARTMENT OF
cout << endl;
return 0;
}
4. Output:
Problem: 5
1. Aim: Construct Binary Tree from Preorder and Inorder Traversal.
2. Objective: Given two integer arrays preorder and inorder where preorder is the preorder traversal of a
binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
3. Code:
#include <iostream>
#include <vector>
#include <queue> // Include the queue header
#include <unordered_map>
#include <sstream>

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };
// Function to build the binary tree from preorder and inorder traversals
TreeNode* buildTreeHelper(vector<int>& preorder, int preStart, int preEnd,
12
DEPARTMENT OF
vector<int>& inorder, int inStart, int inEnd,
unordered_map<int, int>& inMap) { if (preStart > preEnd || inStart >
inEnd) {
return nullptr; // Base case: no elements to construct the tree
}
// The first element in preorder is the root

int rootVal = preorder[preStart];
TreeNode* root = new TreeNode(rootVal);
// Find the index of the root in inorder

int rootIndex = inMap[rootVal];
// Calculate the size of the left subtree

int leftSize = rootIndex - inStart;
// Recursively build the left and right subtrees

root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, rootIndex - 1, inMap); root->right =
buildTreeHelper(preorder, preStart + leftSize + 1, preEnd,
inorder, rootIndex + 1, inEnd, inMap); return root;
}
// Main function to build the binary tree

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> inMap; // Map to store the index of each value in inorder
for (int i = 0; i < inorder.size(); ++i) { inMap[inorder[i]] = i;
}
return buildTreeHelper(preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1, inMap);
}
// Function to perform level order traversal and print the tree

void printLevelOrder(TreeNode* root) {
if (root == nullptr) { cout << "[]";
return;
}
queue<TreeNode*> q; // Declare the queue

13
DEPARTMENT OF
cout << current->val << ",";
} else {
cout << "null,";
}
}
cout << "\b]"; // Remove the last comma
}
int main() {
int n;
cout << "Enter the number of nodes: ";
cin >> n;
vector<int> preorder(n);
vector<int> inorder(n);
cout << "Enter the preorder traversal (space-separated): ";

for (int i = 0; i < n; ++i) {
cin >> preorder[i];
}
cout << "Enter the inorder traversal (space-separated): ";

for (int i = 0; i < n; ++i) { cin >> inorder[i];
}
TreeNode* root = buildTree(preorder, inorder); // Build the binary tree
// Output the constructed binary tree cout <<

"Constructed binary tree (level order): ";
printLevelOrder(root); cout << endl;
return 0;
}
4. Output:
14
DEPARTMENT OF
Problem: 6
1. Aim: Lowest Common Ancestor of a Binary Tree
2. Objective: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the
tree.
The lowest common ancestor is defined between two nodes p and q as the
lowest node in T that has both p and q as descendants (where we allow a node to
be a descendant of itself).
3. Code:
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
15
DEPARTMENT OF
};
// Function to build the binary tree from input

TreeNode* buildBinaryTree(const vector<string>& nodes) {
return nullptr;
}

queue<TreeNode*> q; q.push(root);
int index = 1;


}
index++;

}
index++;
}
return root;
}
// Function to find the lowest common ancestor of two nodes

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) {
return root; // Base case: if root is null or matches p or q
}
TreeNode* left = lowestCommonAncestor(root->left, p, q); // Search in left subtree

TreeNode* right = lowestCommonAncestor(root->right, p, q); // Search in right subtree
16
DEPARTMENT OF
if (left && right) {
return root; // If both left and right are non-null, root is LCA
}
return left ? left : right; // Return the non-null child
}
// Function to find a node in the tree by value TreeNode*

findNode(TreeNode* root, int val) {
if (root == nullptr) return nullptr;
if (root->val == val) return root;
TreeNode* left = findNode(root->left, val);
return left ? left : findNode(root->right, val);
}
int main() {
string input;

}
TreeNode* root = buildBinaryTree(nodes); // Create the binary tree
int pVal, qVal;

cout << "Enter the values of nodes p and q: ";
cin >> pVal >> qVal;
TreeNode* p = findNode(root, pVal);

TreeNode* q = findNode(root, qVal);
if (p && q) {
TreeNode* lca = lowestCommonAncestor(root, p, q); // Find the LCA
cout << "The LCA of nodes " << pVal << " and " << qVal << " is: " << lca->val << endl;
} else {
cout << "One or both of the nodes do not exist in the tree." << endl;
}
return 0;
17
DEPARTMENT OF
}
4. Output:
Problem: 7
1. Aim: Sum Root to Leaf Numbers.
2. Objective: You are given the root of a binary tree containing digits from 0 to 9 only.
• Each root-to-leaf path in the tree represents a number.
• For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
• Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will
fit in 32-bit integer.
• A leaf node is a node with no children.
3. Code:
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
18
DEPARTMENT OF
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
};
TreeNode* createBinaryTree(const vector<string>& nodes) {
return nullptr;
queue<TreeNode*> q;
q.push(root);
int index = 1;
q.pop();

19
DEPARTMENT OF
}
index++;
index++;
return root;
// Function to calculate the sum of all root-to-leaf numbers void
calculateRootToLeafSum(TreeNode* root, int currentSum, int& totalSum) {
if (root == nullptr) { return; // Base
case: if the node is null
// Update the current sum currentSum =
currentSum * 10 + root->val;
// If it's a leaf node, add the current sum to the total sum
20
DEPARTMENT OF
if (root->left == nullptr && root->right == nullptr) {
totalSum += currentSum;
} else {
// Recur for left and right children
calculateRootToLeafSum(root->left, currentSum, totalSum); calculateRootToLeafSum(root-
>right, currentSum, totalSum);
// Main function to calculate the sum of all root-to-leaf numbers
int sumRootToLeafNumbers(TreeNode* root) {
int totalSum = 0;
calculateRootToLeafSum(root, 0, totalSum);
return totalSum;
int main() {
string input; cout << "Enter the binary tree nodes in level order (use 'null' for empty nodes,
space-separated): "; getline(cin, input);
vector<string> nodes;
21
DEPARTMENT OF
string node; while (ss
>> node) {
TreeNode* root = createBinaryTree(nodes); // Create the binary tree
// Calculate the sum of all root-to-leaf numbers int totalSum =
sumRootToLeafNumbers(root); cout << "The total sum of all root-to-leaf
numbers is: " << totalSum << endl;
return 0;
4. Output:
Problem: 8
1. Aim: Populating Next Right Pointers in Each Node.
2. Objective: Given a binary tree
22
DEPARTMENT OF
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node,
the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
3. Code:
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
// Definition for a binary tree node. struct

Node {
int val;
Node *left;
Node *right;
Node *next;
Node(int x) : val(x), left(nullptr), right(nullptr), next(nullptr) {} };

Node* constructBinaryTree(const vector<string>& nodes) {
return nullptr;
}
Node* root = new Node(stoi(nodes[0]));

queue<Node*> q; q.push(root);
int index = 1;

Node* current = q.front();
q.pop();
23
DEPARTMENT OF
current->left = new Node(stoi(nodes[index])); q.push(current-
>left);
}
index++;

current->right = new Node(stoi(nodes[index])); q.push(current-
>right);
}
index++;
}
return root;
}
// Function to connect next right pointers

void populateNextRightPointers(Node* root) {
if (root == nullptr) return;
queue<Node*> q;
q.push(root);
int size = q.size();
Node* prev = nullptr;
for (int i = 0; i < size; ++i) {

q.pop();
if (prev != nullptr) {
prev->next = current; // Connect the previous node's next to the current node
}
prev = current; // Update prev to the current node
// Push left and right children to the queue

if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
// The last node in the level points to NULL
24
DEPARTMENT OF
if (prev != nullptr) {
prev->next = nullptr;
}
}
}
// Function to print the tree level order with next pointers

void displayTreeWithNextPointers(Node* root) {
if (root == nullptr) { cout << "[]";
return;
}
queue<Node*> q;
cout << current->val;
if (current->next) {
cout << " -> " << current->next->val;
} else {
cout << " -> #"; // Indicate the end of the level
}
cout << ", ";
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
}
cout << "\b\b]"; // Remove the last comma and space
}
int main() {
string input;
cout << "Enter
the binary tree
nodes in level
order (use 'null'
for empty nodes,
space-separated):
"; getline(cin,
input);
25
DEPARTMENT OF
}
Node* root = constructBinaryTree(nodes); // Create the binary tree
// Populate next right pointers

populateNextRightPointers(root);
// Output the tree with next pointers

cout << "The tree with next pointers populated: ";
displayTreeWithNextPointers(root);
cout << endl;
return 0;
}
4. Output:
Problem: 9
1. Aim: Count Paths That Can Form a Palindrome in a Tree.
2. Objective: You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted
at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-
indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the
root, parent[0] == -1.
You are also given a string s of length n, where s[i] is the character assigned to the edge
between i and parent[i]. s[0] can be ignored.
Return the number of pairs of nodes (u, v) such that u < v and the characters assigned to
edges on the path from u to v can be rearranged to form a palindrome.
A string is a palindrome when it reads the same backwards as forwards.
26
DEPARTMENT OF
3. Code:
#include <iostream>
#include <vector>
#include <string>
class Solution { public: int

countPairs(vector<int>& parent, string& s) {
int n = parent.size(); vector<vector<int>>
tree(n);
// Build the tree from the parent array

for (int i = 1; i < n; ++i) {
tree[parent[i]].push_back(i);
}
// To store the count of valid pairs

int count = 0;
// Map to store the frequency of character bitmasks

unordered_map<int, int> freqMap; freqMap[0] =
1; // Base case: empty path
// DFS to count pairs

dfs(0, 0, tree, s, freqMap, count);
return count;
}
private:
void dfs(int node, int mask, vector<vector<int>>& tree, string& s, unordered_map<int, int>&
freqMap, int& count) {
// Update the mask for the current character
mask ^= (1 << (s[node] - 'a'));
// Count the number of valid pairs with the current mask

count += freqMap[mask]; // Count pairs with the same mask
for (int i = 0; i < 26; ++i) {
count += freqMap[mask ^ (1 << i)]; // Count pairs with one character different
}
27
DEPARTMENT OF
// Increment the frequency of the current mask
freqMap[mask]++;
// Recur for all children

for (int child : tree[node]) {
dfs(child, mask, tree, s, freqMap, count);
}
// Decrement the frequency of the current mask after returning from DFS
freqMap[mask]--;
}
};
int main() {
int n;
cout << "Enter the number of nodes: ";
cin >> n;
vector<int> parent(n); cout <<

"Enter the parent array: "; for (int
i = 0; i < n; ++i) { cin >>
parent[i];
}
string s;
cout << "Enter the string s: ";
cin >> s;
Solution solution;
int result = solution.countPairs(parent, s);
cout << "The number of valid pairs is: " << result << endl;
return 0;
}
4. Output:
28
DEPARTMENT OF
29

winter camp 2

Uploaded by

Copyright:

Available Formats

winter camp 2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

winter camp 2

Uploaded by

Copyright:

Available Formats

DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Student Name: Lakshay UID: 22BCS16259

1. Aim: Binary Tree Inorder Traversal

using namespace std;

// Definition for a binary tree node.

// Function to perform inorder traversal

// Function to create a binary tree from input

TreeNode* root = new

while (!q.empty() && index < nodes.size())

// Create left child

// Create right child

// Split the input string into a

TreeNode* root = createBinaryTree(nodes); // Create the binary tree

// Output the result cout

using namespace std;

// Definition for a binary tree node.

// Function to calculate the maximum depth of the binary tree

// Function to create a binary tree from input

TreeNode* root = new TreeNode(stoi(nodes[0]));

while (!q.empty() && index < nodes.size()) {

// Create left child

// Create right child

// Split the input string into a vector

TreeNode* root = buildBinaryTree(nodes); // Create the binary tree

int depth = calculateMaxDepth(root); // Calculate the maximum depth

// Output the result

1. Aim: Binary Tree Preorder Traversal

using namespace std;

// Definition for a binary tree node.

// Function to perform preorder traversal

// Function to create a binary tree from input

TreeNode* root = new TreeNode(stoi(nodes[0]));

while (!q.empty() && index < nodes.size()) {

// Create left child

// Split the input string into a vector

TreeNode* root = createBinaryTreeFromInput(nodes); // Create the binary tree

vector<int> result; // Vector to store the preorder traversal result

performPreorderTraversal(root, result); // Perform preorder traversal

// Output the result cout <<

using namespace std;

// Definition for a binary tree node.

// Function to invert the binary tree

return nullptr; // Base case: if the tree is empty

// Recursively invert the left and right subtrees invertBinaryTree(root->left);

// Function to create a binary tree from input

TreeNode* root = new TreeNode(stoi(nodes[0]));

while (!q.empty() && index < nodes.size()) {

// Create left child

// Create right child

// Function to perform level order traversal and print the tree

// Split the input string into a vector

TreeNode* root = constructBinaryTree(nodes); // Create the binary tree

root = invertBinaryTree(root); // Invert the binary tree

// Output the inverted tree cout

using namespace std;

// Definition for a binary tree node.

// The first element in preorder is the root

// Find the index of the root in inorder

// Calculate the size of the left subtree