ADVANCED DATA STRUCTURES ASSIGNMENT

1.Binary Tree Inorder Traversal: EASY

You are given the root of a binary tree, return the inorder traversal of its nodes' values.

Input: root = [1,2,3,4,5,6,7]

Output: [4,2,5,1,6,3,7]

CODE:

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* curr = root;
while (curr != nullptr || !st.empty()) {
while (curr != nullptr) {
st.push(curr);
curr = curr->left;
}
curr = st.top();
st.pop();
result.push_back(curr->val);
curr = curr->right;
}
return result;
}};

EXPLANATION:

First, we create a vector<int> result to store the final answer.
We also create a stack<TreeNode*> st because we are not using recursion, so the stack helps us keep track of nodes.
The pointer curr is used to move through the tree, starting from the root.

We use a while loop that continues as long as either:

• curr is not NULL, or
• the stack is not empty.

Inside the loop:

• We first move as far left as possible.
  While curr is not NULL, we push it onto the stack and move to curr->left.
  We do this because in inorder traversal, we must visit all left nodes before the root.
• When curr becomes NULL, it means we reached the leftmost node.
  So we pop the top node from the stack.
  This node is now ready to be processed, so we add its value to result.
• After processing the node, we move to its right child (curr = curr->right).
  Then the same steps repeat.

2.Binary Tree Preorder Traversal (EASY)

You are given the root of a binary tree, return the preorder traversal of its nodes' values.

Input: root = [1,2,3,null,4,5,null]

Output: [1,2,4,3,5]

CODE:

class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr)
return result;

stack<TreeNode*> st;
st.push(root);

while (!st.empty()) {
TreeNode* node = st.top();
st.pop();

result.push_back(node->val);
if (node->right != nullptr)
st.push(node->right);

if (node->left != nullptr)
st.push(node->left);
}

return result;
}
};

EXPLANATION:

First, we create a vector<int> result to store the traversal output.
If the root is nullptr, we return the empty result immediately because the tree has no nodes.Next, we create a stack<TreeNode*> st and push the root node into it. The stack is used to simulate recursion.

We then run a while loop until the stack becomes empty.

Inside the loop:

We take the top node from the stack and remove it.

• We add its value to result because in preorder traversal we process the root first.
• Then we push its children into the stack.
• We push the right child first.
• Then we push the left child.

We do this because a stack follows Last In, First Out (LIFO).
By pushing the right child first, the left child stays on top of the stack and gets processed next.
This keeps the correct preorder order: Root → Left → Right.

The loop continues until all nodes are processed.

3.Binary Tree Postorder Traversal EASY:

You are given the root of a binary tree, return the postorder traversal of its nodes' values.

Input: root = [1,2,3,4,5,6,7]

Output: [4,5,2,6,7,3,1]

CODE:

class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr)
return result;

stack<TreeNode*> st;
TreeNode* curr = root;
TreeNode* lastVisited = nullptr;

while (curr != nullptr || !st.empty()) {

if (curr != nullptr) {
st.push(curr);
curr = curr->left;
}
else {
TreeNode* topNode = st.top();
if (topNode->right != nullptr && lastVisited != topNode->right) {
curr = topNode->right;
}
else {
result.push_back(topNode->val);
lastVisited = topNode;
st.pop();
} } }

return result;
}};

EXPLANATION:

This code performs postorder traversal, which follows:

Left → Right → Root

We use a stack because we are not using recursion.

• First, we go as left as possible and push nodes into the stack.
• When we can’t go left anymore, we check the right child.
• If the right child exists and hasn’t been visited yet, we move to the right subtree.
• If there is no right child (or it’s already visited), we process the node (add it to result).
• We keep track of the last visited node using lastVisited.

This ensures we only process a node after both its left and right subtrees are done.

4.Missing Number EASY:

Given an array nums containing n integers in the range [0, n] without any duplicates, return the single number in the range that is missing from nums.

Input: nums = [1,2,3]

Output: 0

CODE:

class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();

int expectedSum = n * (n + 1) / 2;
int actualSum = 0;

for (int num : nums) {
actualSum += num;
}
return expectedSum — actualSum;
}
};

EXPLANATION:

• First, find how many numbers are in the array (n).
• Calculate what the total sum should be from 0 to n.
• Then calculate the actual sum of elements in the array.
• Subtract both sums.
• The difference is the missing number.

5) Insert into a Binary Search Tree (MEDIUM):

You are given the root node of a binary search tree (BST) and a value val to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Input: root = [5,3,9,1,4], val = 6

Output: [5,3,9,1,4,6]

CODE:

class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
return new TreeNode(val);
}
if (val < root->val) {
root->left = insertIntoBST(root->left, val);
} else {
root->right = insertIntoBST(root->right, val);
}
return root;
}};

EXPLANATION:

The function adds a new value into a Binary Search Tree.

It starts at the root (top node).

• If the new value is smaller than the current node’s value, it moves to the left child.
• If the new value is greater, it moves to the right child.

It keeps moving left or right until it finds an empty spot (where the node is nullptr). When it finds that empty spot, it creates a new node with the given value and places it there.Finally, it returns the original root so the whole tree remains connected.

6.Delete Node in a BST (MEDIUM):

You are given a root node reference of a BST and a key, delete the node with the given key in the BST, if present. Return the root node reference (possibly updated) of the BST.

Input: root = [5,3,9,1,4], key = 3

Output: [5,4,9,1]

CODE:

class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return nullptr;

if (key < root->val) {
root->left = deleteNode(root->left, key);
}
else if (key > root->val) {
root->right = deleteNode(root->right, key);
}
else {
if (root->left == nullptr && root->right == nullptr) {
delete root;
return nullptr;
}
if (root->left == nullptr) {
TreeNode* temp = root->right;
delete root;
return temp;
}
if (root->right == nullptr) {
TreeNode* temp = root->left;
delete root;
return temp;
}
TreeNode* successor = root->right;
while (successor->left != nullptr) {
successor = successor->left;
}root->val = successor->val;
root->right = deleteNode(root->right, successor->val);
}return root;
}
};

EXPLANATION:

To delete a node in a Binary Search Tree, first you search for the node using the BST rule:

• If the key is smaller than the current node, move left.
• If the key is greater, move right.
  Keep doing this until you find the node.

Once you find the node, there are three possible situations:

First, if the node has no children, you simply remove it.

Second, if the node has one child, you remove the node and connect its parent directly to its only child.

Get SAISINDUJAA S’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Third, if the node has two children, you cannot remove it directly because that would break the BST rule. So instead, you find the smallest value in its right subtree. Replace the node’s value with that smallest value. Then delete that smallest value node from the right subtree.

7. Implement Trie (Prefix Tree) : MEDIUM

A prefix tree (also known as a trie) is a tree data structure used to efficiently store and retrieve keys in a set of strings. Some applications of this data structure include auto-complete and spell checker systems.

Input:
["Trie", "insert", "dog", "search", "dog", "search", "do", "startsWith", "do", "insert", "do", "search", "do"]

Output:
[null, null, true, false, true, null, true]

Explanation:
PrefixTree prefixTree = new PrefixTree();
prefixTree.insert("dog");
prefixTree.search("dog");    // return true
prefixTree.search("do");     // return false
prefixTree.startsWith("do"); // return true
prefixTree.insert("do");
prefixTree.search("do");     // return true

CODE:

class PrefixTree {
private:
struct TrieNode {
TrieNode* children[26];
bool isEnd;

TrieNode() {
isEnd = false;
for (int i = 0; i < 26; i++)
children[i] = nullptr;
}
};

TrieNode* root;

public:
PrefixTree() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* node = root;

for (char c : word) {
int index = c — ‘a’;

if (node->children[index] == nullptr) {
node->children[index] = new TrieNode();
}

node = node->children[index];
}

node->isEnd = true;
}

bool search(string word) {
TrieNode* node = root;

for (char c : word) {
int index = c — ‘a’;

if (node->children[index] == nullptr)
return false;

node = node->children[index];
}

return node->isEnd;
}

bool startsWith(string prefix) {
TrieNode* node = root;

for (char c : prefix) {
int index = c — ‘a’;

if (node->children[index] == nullptr)
return false;

node = node->children[index];
}

return true;
}};

EXPLANATION:

Insert a word

• Start from the root.
• For each letter in the word:
• Convert the letter to an index (c - 'a').
• If the corresponding child does not exist, create a new node.
• Move to that child node.
• After the last letter, mark isEnd = true to indicate a complete word.

Search for a word

• Start from the root.
• For each letter:
• Convert to index and move to the corresponding child.
• If a child does not exist, the word is not in the Trie → return false.
• After the last letter, return true only if isEnd is true (to ensure it’s a complete word).

Check if a prefix exists (startsWith)

• Start from the root.
• For each letter in the prefix:
• Move to the corresponding child node.
• If a child does not exist, return false.
• If all letters are found, return true (the prefix exists in the Trie).
• No need to check isEnd because it may just be the start of a longer word.

8. Word Search II : (HARD)

Given a 2-D grid of characters board and a list of strings words, return all words that are present in the grid.For a word to be present it must be possible to form the word with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Input:
board = [
  ["a","b","c","d"],
  ["s","a","a","t"],
  ["a","c","k","e"],
  ["a","c","d","n"]
],
words = ["bat","cat","back","backend","stack"]

Output: ["cat","back","backend"]

CODE:

class Solution {
private:
struct TrieNode {
TrieNode* children[26];
string word;

TrieNode() : word(“”) {
for (int i = 0; i < 26; i++)
children[i] = nullptr;
} };
TrieNode* buildTrie(const vector<string>& words) {
TrieNode* root = new TrieNode();
for (const string& word : words) {
TrieNode* node = root;
for (char ch : word) {
int index = ch — ‘a’;
if (!node->children[index])
node->children[index] = new TrieNode();
node = node->children[index];
} node->word = word; // mark end of a word
} return root;
}
void dfs(vector<vector<char>>& board, int row, int col, TrieNode* node, vector<string>& result) {
char current = board[row][col];
if (current == ‘#’ || !node->children[current — ‘a’])
return;

node = node->children[current — ‘a’];

if (!node->word.empty()) {
result.push_back(node->word);
node->word = “”; // avoid duplicates
}
board[row][col] = ‘#’;

int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
for (auto& dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];

if (newRow >= 0 && newRow < board.size() &&
newCol >= 0 && newCol < board[0].size()) {
dfs(board, newRow, newCol, node, result);
} }
board[row][col] = current;
}

public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> result;
TrieNode* trieRoot = buildTrie(words);

int rows = board.size();
int cols = board[0].size();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
dfs(board, i, j, trieRoot, result);
} }

return result;
}};

EXPLANATION:

Step 1: Build a Trie

• Each node has 26 children for letters a to z.
• Each node also stores word if a word ends there.
• Insert every word from the list:
• For each letter in the word, move/create a child node.
• At the last letter, store the full word in word.

This allows us to quickly check:

• If a path in the board could lead to a word (prefix exists)
• If a word is completed (node contains a word)

Step 2: DFS Traversal

• Start DFS from every cell in the board.
• At each step:

1. Check if the current letter exists in the Trie node.

• If not → stop exploring this path.
• If the Trie node contains a word → add it to the result.
• Clear node->word to avoid duplicates.

Mark the current cell as visited by setting it to #.

Move to all four neighbors: up, down, left, right.

After exploring neighbors → backtrack by restoring the cell’s original letter.

9. Word Break II : (HARD)

You are given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Input: s = "neetcode", wordDict = ["neet","code"]

Output: ["neet code"]

CODE:

class Solution {
private:
unordered_set<string> wordSet;
unordered_map<int, vector<string>> memo;
vector<string> backtrack(const string& s, int start) {

if (memo.count(start)) return memo[start];

vector<string> sentences;
if (start == s.size()) {
sentences.push_back(“”);
return sentences;
}
for (int end = start + 1; end <= s.size(); end++) {
string word = s.substr(start, end — start);
if (wordSet.count(word)) {
vector<string> nextParts = backtrack(s, end);
for (string& part : nextParts) {
if (part.empty())
sentences.push_back(word); // last word
else
sentences.push_back(word + “ “ + part);
} } }
memo[start] = sentences;
return sentences;
}public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
wordSet = unordered_set<string>(wordDict.begin(), wordDict.end());
memo.clear();
return backtrack(s, 0);
}
};

EXPLANATION:

Dictionary lookup:

• The words from wordDict are stored in a set for O(1) lookup.

Recursive function (backtrack):

• This function tries to form all valid sentences starting from a given index in s.
• For the current substring, it checks every possible prefix: if the prefix is a valid word, it recursively finds all sentences for the remaining substring.
• Then it combines the current word with the results from recursion to build complete sentences.

Memoization:

• Results for each starting index are stored in a map (memo) so that if the function is called again with the same index, it can return the cached result immediately.
• This avoids recomputation and makes the solution efficient.

Backtracking:

• By recursively exploring all valid prefixes and combining them with subsequent results, the code explores all possible sentence splits without missing any.

Return value:

• After recursion is complete, the function returns a list of all valid sentences.
• Sentences are built by joining words with spaces.