Binary tree
Binary Trees¶
Binary Trees are hierarchical data structures where each node has at most two children — a left child and a right child. They are widely used in searching, sorting, hierarchical data representation, and expression parsing.
1. Tree Traversals¶
Traversals are techniques used to visit every node in a tree in a specific order. They form the foundation for most binary tree algorithms.
/*
Question:
Given an integer 'N', determine the maximum number of nodes present on 'Nth' level in a binary tree.
Approach:
- The number of nodes on each level of a binary tree follows a pattern.
- The number of nodes on the Nth level is equal to 2^(N-1).
- We can use the pow function from the cmath library to calculate the power of 2.
Complexity Analysis:
- The time complexity of this approach is O(1) as we are using a simple mathematical formula.
- The space complexity is also O(1) as we are not using any additional space.
Code:
*/
int numberOfNodes(int N) {
if(N <= 1) {
return 1;
}
return pow(2, N - 1);
}
/*
Question:
You are given an array nodes. It contains 7 integers, which represents the value of nodes of the binary tree in level order traversal. You are also given a root of the tree which has a value equal to nodes[0].
Your task to construct a binary tree by creating nodes for the remaining 6 nodes.
Approach:
- We can solve this problem recursively by performing a level-order traversal of the tree.
- Starting from the root node, we can recursively create the left and right child nodes using the given array of values.
- The position of each child node in the array can be calculated based on the index of its parent node.
Complexity Analysis:
- Since we are visiting each node once, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N) as we are using the call stack for recursion.
Code:
*/
struct node {
int data;
node* left;
node* right;
};
node* newNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
node* solve(vector<int>& vec, int i) {
if(i >= 7) {
return NULL;
}
node* root = newNode(vec[i]);
i = 2 * i;
root->left = solve(vec, i + 1);
root->right = solve(vec, i + 2);
return root;
}
void create_tree(node*& root0, vector<int>& vec) {
root0 = solve(vec, 0);
}
/*
Question:
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Approach:
- Preorder traversal visits the root node first, followed by the left subtree, and then the right subtree.
- We can solve this problem recursively by following the preorder traversal order.
- Starting from the root node, we can add the node's value to the result vector, then recursively traverse the left subtree and right subtree.
Complexity Analysis:
- Since we are visiting each node once, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N) as we are using the call stack for recursion.
Code:
*/
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
solve(root, ans);
return ans;
}
void solve(TreeNode* root, vector<int>& ans) {
if (!root) {
return;
}
ans.push_back(root->val);
solve(root->left, ans);
solve(root->right, ans);
}
/*
Question:
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Approach:
- inorder traversal visits the left subtree first, followed by the root node, and then the right subtree.
- We can solve this problem recursively by following the inorder traversal order.
Complexity Analysis:
- Since we are visiting each node once, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N) as we are using the call stack for recursion.
Code:
*/
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
solve(root, ans);
return ans;
}
void solve(TreeNode* root, vector<int>& ans) {
if (!root) {
return;
}
solve(root->left, ans);
ans.push_back(root->val);
solve(root->right, ans);
}
/*
Question:
Given the root of a binary tree, return the postorder traversal of its nodes' values.
Approach:
- postorder traversal visits the left subtree first, followed by the right subtree, and then the root node.
- We can solve this problem recursively by following the postorder traversal order.
Complexity Analysis:
- Since we are visiting each node once, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N) as we are using the call stack for recursion.
Code:
*/
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
solve(root, ans);
return ans;
}
void solve(TreeNode* root, vector<int>& ans) {
if (!root) {
return;
}
solve(root->left, ans);
ans.push_back(root->val);
solve(root->right, ans);
}
/*
Question:
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Approach:
- We can perform a level order traversal using a queue.
- We start by pushing the root node into the queue.
- Then, while the queue is not empty, we process each level by taking the size of the queue and iterating over the nodes at that level.
- For each node, we add its value to the current level's vector and push its left and right child nodes into the queue if they exist.
- After processing each level, we add the level's vector to the result vector.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N) as we store the node values in the result vector.
Code:
*/
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) {
return ans;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> level;
int n = q.size();
for (int i = 0; i < n; i++) {
TreeNode* curr = q.front();
q.pop();
level.push_back(curr->val);
if (curr->left) {
q.push(curr->left);
}
if (curr->right) {
q.push(curr->right);
}
}
ans.push_back(level);
}
return ans;
}
/*
Question:
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Approach:
- We can perform a preorder traversal iteratively using a stack.
- We start by pushing the root node into the stack.
- Then, while the stack is not empty, we pop a node from the stack, add its value to the result vector, and push its right child (if it exists) followed by its left child (if it exists) into the stack.
- By pushing the right child before the left child, we ensure that the left child is processed first during the traversal.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N) as we store the node values in the result vector.
Code:
*/
vector<int> preorderTraversal(TreeNode* root) {
if (!root) {
return {};
}
stack<TreeNode*> st;
st.push(root);
vector<int> ans;
while (!st.empty()) {
TreeNode* curr = st.top();
st.pop();
ans.push_back(curr->val);
if (curr->right) {
st.push(curr->right);
}
if (curr->left) {
st.push(curr->left);
}
}
return ans;
}
/*
Question:
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Approach:
- We can perform an inorder traversal iteratively using a stack.
- The idea is to push all the left children of a node into the stack until we reach a node with no left child.
- Then, we pop a node from the stack, add its value to the result vector, and move to its right child (if it exists).
- We repeat this process until the stack is empty and all nodes are traversed.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N) as we store the node values in the result vector and use a stack to keep track of the nodes.
Code:
*/
void pushLeft(TreeNode* curr, stack<TreeNode*>& st) {
while (curr) {
st.push(curr);
curr = curr->left;
}
}
vector<int> inorderTraversal(TreeNode* root) {
if (!root) {
return {};
}
stack<TreeNode*> st;
TreeNode* curr = root;
pushLeft(curr, st);
vector<int> ans;
while (!st.empty()) {
curr = st.top();
st.pop();
ans.push_back(curr->val);
curr = curr->right;
if (curr) {
pushLeft(curr, st);
}
}
return ans;
}
/*
Question:
Given the root of a binary tree, return the postorder traversal of its nodes' values.
Approach:
- We can perform a postorder traversal iteratively using a stack and a map.
- The idea is to push all the left children of a node into the stack until we reach a node with no left child.
- Then, we check if the right child of the node exists or has already been visited (using the map).
- If it does not exist or has been visited, we add the node's value to the result vector and pop the node from the stack.
- Otherwise, we push the right child into the stack and mark it as visited in the map.
- We repeat this process until the stack is empty and all nodes are traversed.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is also O(N) as we store the node values in the result vector and use a stack and a map to keep track of the nodes.
Code:
*/
void pushLeft(TreeNode* curr, stack<TreeNode*>& st, unordered_map<TreeNode*, bool>& mp) {
while (curr) {
mp[curr] = true;
st.push(curr);
curr = curr->left;
}
}
vector<int> postorderTraversal(TreeNode* root) {
if (!root) {
return {};
}
vector<int> ans;
stack<TreeNode*> st;
TreeNode* curr = root;
unordered_map<TreeNode*, bool> mp;
pushLeft(curr, st, mp);
while (!st.empty()) {
curr = st.top();
if (!curr->right || mp[curr->right]) {
ans.push_back(curr->val);
st.pop();
}
else {
pushLeft(curr->right, st, mp);
}
}
return ans;
}
/*
Question:
You have been given a Binary Tree of 'N' nodes, where the nodes have integer values.
Your task is to find the In-Order, Pre-Order, and Post-Order traversals of the given binary tree.
Approach:
- We can perform the tree traversals recursively using three functions:
- In-Order Traversal: Visit the left subtree, visit the current node, visit the right subtree.
- Pre-Order Traversal: Visit the current node, visit the left subtree, visit the right subtree.
- Post-Order Traversal: Visit the left subtree, visit the right subtree, visit the current node.
- For each traversal, we can maintain a vector to store the values of the visited nodes in the respective order.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N) as we store the values of the nodes in vectors for each traversal.
Code:
*/
void traversal(BinaryTreeNode<int>* root, vector<int>& pre, vector<int>& ino, vector<int>& pos) {
if (root == NULL) {
return;
}
// Pre-Order Traversal
pre.push_back(root->data);
traversal(root->left, pre, ino, pos);
// In-Order Traversal
ino.push_back(root->data);
traversal(root->right, pre, ino, pos);
// Post-Order Traversal
pos.push_back(root->data);
}
vector<vector<int>> getTreeTraversal(BinaryTreeNode<int>* root) {
vector<vector<int>> ans;
vector<int> pre;
vector<int> ino;
vector<int> pos;
traversal(root, pre, ino, pos);
ans.push_back(ino);
ans.push_back(pre);
ans.push_back(pos);
return ans;
}
2. Medium Problems¶
/*
Question:
Given the root of a binary tree, return its maximum depth.
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.
Approach:
- We can calculate the maximum depth of a binary tree recursively by traversing its left and right subtrees.
- The maximum depth of a tree is equal to the maximum of the maximum depths of its left and right subtrees, plus 1 for the root node.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(H), where H is the height of the binary tree. In the worst case, the tree can be skewed and have a height of N, resulting in O(N) space complexity. In the best case, the tree is balanced and has a height of log(N), resulting in O(log(N)) space complexity.
Code:
*/
int maxDepth(TreeNode* root) {
if (!root) {
return 0;
}
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
/*
Question:
Given a binary tree, determine if it is height-balanced.
Approach:
- We can solve this problem recursively by checking if the left and right subtrees of each node are height-balanced.
- For each node, we calculate the height of its left and right subtrees, and check if the absolute difference of their heights is at most 1.
- If both subtrees are height-balanced, and the absolute difference of their heights is at most 1, then the current node and its subtree are height-balanced.
- We can use a pair of values to represent the result of the recursion: the first value indicates if the subtree is height-balanced, and the second value represents the height of the subtree.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(H), where H is the height of the binary tree. In the worst case, the tree can be skewed and have a height of N, resulting in O(N) space complexity. In the best case, the tree is balanced and has a height of log(N), resulting in O(log(N)) space complexity.
Code:
*/
pair<bool, int> solve(TreeNode* root) {
if (!root) {
return {true, 0};
}
auto left = solve(root->left);
auto right = solve(root->right);
int height = max(left.second, right.second) + 1;
bool balanced = left.first && right.first && abs(left.second - right.second) <= 1;
return {balanced, height};
}
bool isBalanced(TreeNode* root) {
auto result = solve(root);
return result.first;
}
/*
Question:
Given the root of a binary tree, return the length of the diameter of the tree.
Approach:
- The diameter of a binary tree is the length of the longest path between any two nodes in the tree.
- This path may or may not pass through the root.
- To find the diameter of the tree, we can recursively calculate the height of each node's left and right subtrees.
- At each node, we calculate the diameter as the maximum of the following three values:
- The diameter of the left subtree.
- The diameter of the right subtree.
- The sum of the heights of the left and right subtrees plus one (for the current node).
- We update the diameter variable with the maximum diameter encountered during the traversal.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(H), where H is the height of the binary tree. In the worst case, the tree can be skewed and have a height of N, resulting in O(N) space complexity. In the best case, the tree is balanced and has a height of log(N), resulting in O(log(N)) space complexity.
Code:
*/
int maxDepth(TreeNode* root, int& diameter) {
if (!root) {
return 0;
}
int left = maxDepth(root->left, diameter);
int right = maxDepth(root->right, diameter);
diameter = max(diameter, left + right);
return max(left, right) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
maxDepth(root, diameter);
return diameter;
}
/*
Question:
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them.
A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node's values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Approach:
- The maximum path sum can be calculated using a recursive approach.
- For each node, we calculate the maximum path sum that includes the node as the root.
- The maximum path sum that includes the current node is the maximum of the following values:
- The value of the current node.
- The maximum path sum of the left subtree plus the value of the current node.
- The maximum path sum of the right subtree plus the value of the current node.
- The maximum path sum of the left subtree plus the maximum path sum of the right subtree plus the value of the current node.
- During the calculation, we keep track of the maximum path sum encountered so far and update it if necessary.
- We return the maximum path sum encountered overall.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(H), where H is the height of the binary tree. In the worst case, the tree can be skewed and have a height of N, resulting in O(N) space complexity. In the best case, the tree is balanced and has a height of log(N), resulting in O(log(N)) space complexity.
Code:
*/
int solve(TreeNode* root, int& maxSum) {
if (!root) {
return 0;
}
int leftSum = max(0, solve(root->left, maxSum));
int rightSum = max(0, solve(root->right, maxSum));
int currentSum = root->val + leftSum + rightSum;
maxSum = max(maxSum, currentSum);
return root->val + max(leftSum, rightSum);
}
int maxPathSum(TreeNode* root) {
int maxSum = INT_MIN;
solve(root, maxSum);
return maxSum;
}
/*
Question:
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Approach:
- The trees are considered the same if they have the same structure (i.e., same nodes in the same arrangement) and the corresponding nodes have the same values.
- We can use a recursive approach to check if the trees are the same.
- The trees are the same if both trees are empty (reached the end of the tree) or both trees are non-empty and the current nodes have the same value, and the left subtrees and right subtrees are the same.
- We can check if the trees are the same by comparing the values of the current nodes and recursively checking the left subtrees and right subtrees.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(H), where H is the height of the binary tree. In the worst case, the tree can be skewed and have a height of N, resulting in O(N) space complexity. In the best case, the tree is balanced and has a height of log(N), resulting in O(log(N)) space complexity.
Code:
*/
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) {
return true; // Both trees are empty, they are the same
}
if (!p || !q) {
return false; // One tree is empty and the other is not, they are different
}
return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
/*
Question:
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Approach:
- We can use a queue to perform a level order traversal of the binary tree.
- To achieve the zigzag order, we can use a flag variable to keep track of the current direction (left to right or right to left) for each level.
- Initialize a boolean variable `ltor` to true, where true represents the left to right direction.
- While traversing each level, we store the values of the nodes in a temporary vector.
- If `ltor` is true, we push the left child first and then the right child into the queue for the next level.
- If `ltor` is false, we push the right child first and then the left child into the queue for the next level.
- After processing all the nodes in the current level, if `ltor` is false, we reverse the temporary vector to achieve the right to left direction for the next level.
- We alternate the value of `ltor` after processing each level to switch between left to right and right to left directions.
- Finally, we return the vector containing the zigzag level order traversal.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(M), where M is the maximum number of nodes at any level in the binary tree. In the worst case, the maximum number of nodes at any level can be N/2 (in a complete binary tree), resulting in O(N) space complexity.
Code:
*/
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return {}; // Empty tree, return an empty vector
vector<vector<int>> ans; // Vector to store the zigzag level order traversal
queue<TreeNode*> q; // Queue for level order traversal
q.push(root);
bool ltor = true; // Flag variable to track the current direction (left to right or right to left)
while (!q.empty()) {
int n = q.size(); // Number of nodes at the current level
vector<int> levelValues; // Temporary vector to store the values of nodes at the current level
for (int i = 0; i < n; i++) {
TreeNode* curr = q.front();
q.pop();
levelValues.push_back(curr->val);
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
if (!ltor) {
reverse(levelValues.begin(), levelValues.end()); // Reverse the values to achieve right to left direction
}
ans.push_back(levelValues);
ltor = !ltor; // Alternate the direction for the next level
}
return ans;
}
/*
Question:
Given a Binary Tree, find its Boundary Traversal. The traversal should be in the following order:
Left boundary nodes: defined as the path from the root to the left-most node, i.e., the leaf node you could reach when you always travel preferring the left subtree over the right subtree.
Leaf nodes: All the leaf nodes except for the ones that are part of the left or right boundary.
Reverse right boundary nodes: defined as the path from the right-most node to the root. The right-most node is the leaf node you could reach when you always travel preferring the right subtree over the left subtree. Exclude the root from this as it was already included in the traversal of left boundary nodes.
Note: If the root doesn't have a left subtree or right subtree, then the root itself is the left or right boundary.
Approach:
- We can divide the boundary traversal into three parts: left boundary nodes, leaf nodes, and reverse right boundary nodes.
- To find the left boundary nodes, we can traverse the left subtree from the root to the leftmost leaf node. We add the values of the nodes to the answer vector during this traversal.
- To find the leaf nodes, we can perform a separate recursive traversal of the binary tree and add the values of the leaf nodes (excluding the ones already included in the left boundary or right boundary) to the answer vector.
- To find the reverse right boundary nodes, we can traverse the right subtree from the root to the rightmost leaf node (excluding the root). We add the values of the nodes to the answer vector during this traversal.
- Finally, we return the answer vector containing the boundary traversal.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(H), where H is the height of the binary tree. In the worst case, the height of the binary tree can be N, resulting in O(N) space complexity.
Code:
*/
void leftTraversal(TreeNode<int>* root, vector<int>& ans) {
if (!root) return;
if (!root->left && !root->right) return;
ans.push_back(root->val);
if (root->left)
leftTraversal(root->left, ans);
else
leftTraversal(root->right, ans);
}
void leafTraversal(TreeNode<int>* root, vector<int>& ans) {
if (!root) return;
if (!root->left && !root->right) {
ans.push_back(root->val);
}
leafTraversal(root->left, ans);
leafTraversal(root->right, ans);
}
void rightTraversal(TreeNode<int>* root, vector<int>& ans) {
if (!root) return;
if (!root->left && !root->right) return;
int temp = root->val;
if (root->right)
rightTraversal(root->right, ans);
else
rightTraversal(root->left, ans);
ans.push_back(temp);
}
vector<int> boundaryTraversal(TreeNode<int>* root) {
if (!root) return {};
vector<int> ans;
ans.push_back(root->val);
leftTraversal(root->left, ans);
leafTraversal(root->left, ans);
leafTraversal(root->right, ans);
rightTraversal(root->right, ans);
return ans;
}
/*
Question:
Given the root of a binary tree, calculate the vertical order traversal of the binary tree.
There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
Approach:
- We can perform a level order traversal of the binary tree while keeping track of the horizontal distance (hd) of each node from the root.
- For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively.
- We can use a queue to perform the level order traversal. The queue will store pairs of (hd, node), where hd represents the horizontal distance and node represents the current node being processed.
- During the traversal, we maintain an unordered_map to store the nodes at each horizontal distance. The key in the map is the horizontal distance (hd), and the value is a vector of pairs representing the level and value of the nodes at that horizontal distance.
- After the traversal, we iterate over the keys in the map in ascending order and sort the nodes within each horizontal distance based on their levels. We then extract the values and add them to the result vector.
- Finally, we return the result vector containing the vertical order traversal.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N), where N is the number of nodes in the binary tree. This space is used to store the nodes in the unordered_map during the traversal.
Code:
*/
// NOTE:- we are keeping track of levels because of the question condition but if no such condition exists, then no need of level only hd will work.
vector<vector<int>> verticalTraversal(TreeNode* root) {
if (!root) return {};
unordered_map<int, vector<pair<int, int>>> mp;
int mini = 0, maxi = 0;
queue<pair<int, TreeNode*>> q;
q.push({0, root});
int lvl = 0;
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
auto p = q.front();
q.pop();
TreeNode* curr = p.second;
int hd = p.first;
if (curr->left) {
mini = min(mini, hd - 1);
q.push({hd - 1, curr->left});
}
if (curr->right) {
maxi = max(maxi, hd + 1);
q.push({hd + 1, curr->right});
}
mp[hd].push_back({lvl, curr->val});
}
lvl++;
}
vector<vector<int>> ans;
for (int i = mini; i <= maxi; i++) {
sort(mp[i].begin(), mp[i].end());
vector<int> temp;
for (auto it : mp[i])
temp.push_back(it.second);
ans.push_back(temp);
}
return ans;
}
/*
Question:
Given a binary tree, print its top view.
Approach:
- We can perform a level order traversal of the binary tree while keeping track of the horizontal distance (hd) of each node from the root.
- For each node, if the horizontal distance is not present in the map, we add it to the map along with its value.
- Since we want to print the nodes in the order of their horizontal distance, we maintain the minimum and maximum horizontal distances (`mini` and `maxi`) during the traversal.
- Finally, we iterate over the range from `mini` to `maxi` and retrieve the corresponding values from the map, and add them to the result vector.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N), where N is the number of nodes in the binary tree. This space is used to store the nodes in the map during the traversal.
Code:
*/
vector<int> getTopView(TreeNode<int> *root) {
if (!root) return {};
unordered_map<int, int> mp;
int mini = 0, maxi = 0;
queue<pair<int, TreeNode<int>*>> q;
q.push({0, root});
while (!q.empty()) {
auto p = q.front();
q.pop();
TreeNode<int>* curr = p.second;
int hd = p.first;
if (curr->left) {
mini = min(mini, hd - 1);
q.push({hd - 1, curr->left});
}
if (curr->right) {
maxi = max(maxi, hd + 1);
q.push({hd + 1, curr->right});
}
if (mp.find(hd) == mp.end())
mp[hd] = curr->data;
}
vector<int> ans;
for (int i = mini; i <= maxi; i++) {
ans.push_back(mp[i]);
}
return ans;
}
/*
Question:
Given a binary tree, print its bottom view.
Approach:
- We can perform a level order traversal of the binary tree while keeping track of the horizontal distance (hd) and the level of each node from the root.
- For each node, we update its horizontal distance and level in the map.
- Since we want to print the nodes in the order of their horizontal distance, we maintain the minimum and maximum horizontal distances (`mini` and `maxi`) during the traversal.
- Finally, we iterate over the range from `mini` to `maxi` and retrieve the corresponding values from the map, and add them to the result vector.
Complexity Analysis:
- Since we visit each node once and perform constant time operations for each node, the time complexity of this approach is O(N), where N is the number of nodes in the binary tree.
- The space complexity is O(N), where N is the number of nodes in the binary tree. This space is used to store the nodes in the map during the traversal.
Code:
*/
vector<int> getBottomView(TreeNode<int> *root) {
if (!root) return {};
unordered_map<int, pair<int, int>> mp;
int mini = 0, maxi = 0;
queue<pair<TreeNode<int>*, pair<int, int>>> q;
q.push({root, {0, 0}});
while (!q.empty()) {
auto p = q.front();
q.pop();
TreeNode<int>* curr = p.first;
int hd = p.second.first;
int level = p.second.second;
mp[hd] = {curr->data, level};
mini = min(mini, hd);
maxi = max(maxi, hd);
if (curr->left) {
q.push({curr->left, {hd - 1, level + 1}});
}
if (curr->right) {
q.push({curr->right, {hd + 1, level + 1}});
}
}
vector<int> ans;
for (int i = mini; i <= maxi; i++) {
ans.push_back(mp[i].first);
}
return ans;
}
/*
Question: Given the root of a binary tree, imagine yourself standing on the right side of it,
return the values of the nodes you can see ordered from top to bottom.
*/
/*
Approach:
- Perform a level order traversal of the binary tree.
- For each level, keep track of the last node encountered (the rightmost node from the viewer's perspective).
- Add the value of the last node at each level to the result.
Complexity Analysis:
- Time complexity: O(N), where N is the number of nodes in the binary tree.
- Space complexity: O(M), where M is the maximum number of nodes at any level in the tree.
CODE:-
*/
vector<int> rightSideView(TreeNode* root) {
if (!root) return {};
vector<int> ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
TreeNode* curr = q.front();
q.pop();
if (curr->left) {
q.push(curr->left);
}
if (curr->right) {
q.push(curr->right);
}
// Add only the last node of the level to the answer for right view in case of left view push only the first element
if (i == n - 1) {
ans.push_back(curr->val);
}
}
}
return ans;
}
/**
QUESTION:
Given the root of a binary tree, check whether it is a mirror of itself
(i.e., symmetric around its center).
Example:
Input: root = [1,2,2,3,4,4,3]
Output: true
*/
/**
APPROACH:
We can solve this problem using a recursive approach.
1. Define a helper function "isMirror" that takes two tree nodes as input.
2. Base case:
- If both nodes are NULL, return true.
- If either node is NULL, return false.
3. Check if the values of the two nodes are equal.
4. Recursively call "isMirror" on the left and right children of the two nodes:
- isMirror(node1->left, node2->right)
- isMirror(node1->right, node2->left)
5. Return the logical AND of the above two recursive calls.
6. In the main "isSymmetric" function, return the result of calling "isMirror" on the root's left and right children.
COMPLEXITY ANALYSIS:
- The time complexity is O(N), where N is the number of nodes in the binary tree, as we need to visit all the nodes once.
- The space complexity is O(H), where H is the height of the tree, due to the recursive function calls on the stack.
In the worst case, the height of the tree can be equal to the number of nodes, resulting in O(N) space complexity.
CODE:-
*/
bool isMirror(TreeNode* node1, TreeNode* node2) {
if (!node1 && !node2)
return true;
if (!node1 || !node2)
return false;
return (node1->val == node2->val) &&
isMirror(node1->left, node2->right) &&
isMirror(node1->right, node2->left);
}
bool isSymmetric(TreeNode* root) {
return isMirror(root->left, root->right);
}
3. Hard Problems¶
/**Question:**
Write a program to print the path from the root to a given node in a binary tree. You are given a binary tree and a node value. You need to find and print the path from the root to the node.
**Approach:**
To find the path from the root to the given node, we can use a recursive function. The idea is to traverse the tree from the root and keep track of the path in a vector. If the target node is found, add the node's value to the path vector, and return true. Otherwise, recursively search for the target node in the left and right subtrees. If the target node is not found, remove the last node from the path vector before returning false.
**Complexity Analysis:**
Let N be the number of nodes in the binary tree.
- Time Complexity: The time complexity of the recursive function is O(N) as we may visit all nodes in the worst case.
- Space Complexity: The space complexity is O(N) due to the space used by the recursion stack and the path vector.
**Code:**/
bool findPath(TreeNode* root, int target, vector<int>& path) {
if (!root) return false;
path.push_back(root->val);
if (root->val == target) {
return true;
}
if (findPath(root->left, target, path) || findPath(root->right, target, path)) {
return true;
}
path.pop_back();
return false;
}
vector<int> getPathFromRootToNode(TreeNode* root, int target) {
vector<int> path;
findPath(root, target, path);
return path;
}
/* QUESTION:
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: "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)."
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
APPROACH:
To find the lowest common ancestor (LCA) of two nodes `p` and `q` in a binary tree, we can use a recursive approach. We start from the root of the tree and check if either `p` or `q` matches the current node. If one of them matches, it means that the current node is the LCA. Otherwise, we recursively search for `p` and `q` in the left and right subtrees.
COMPLEXITY ANALYSIS:
Let `n` be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n) since we may have to visit all nodes of the binary tree in the worst case.
- Space Complexity: The space complexity is O(h) for the recursive call stack, where `h` is the height of the binary tree. In the worst case, when the binary tree is skewed, the space complexity becomes O(n).
CODE:
*/
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return NULL;
if (root->val == p->val || root->val == q->val) return root;
TreeNode* lef = lowestCommonAncestor(root->left, p, q);
TreeNode* rig = lowestCommonAncestor(root->right, p, q);
if (!lef)
return rig;
if (!rig)
return lef;
return root;
}
/* QUESTION:
Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
It is guaranteed that the answer will be in the range of a 32-bit signed integer.
Example 1:
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).
APPROACH:
To find the maximum width, we can perform a level-order traversal (BFS) of the binary tree while keeping track of the indices of nodes at each level. For each level, we calculate the width by finding the difference between the indices of the leftmost and rightmost non-null nodes. The maximum width among all levels will be the answer.
COMPLEXITY ANALYSIS:
Let `n` be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n) since we need to traverse all nodes in the binary tree using BFS.
- Space Complexity: The space complexity is O(w) for the queue, where `w` is the maximum width of the binary tree at any level.
CODE:
*/
int widthOfBinaryTree(TreeNode* root) {
if (!root) return 0;
long long ans = 0;
queue<pair<long long, TreeNode*>> q;
q.push({0, root});
while (!q.empty()) {
int n = q.size();
long long start = q.front().first;
long long end = q.back().first;
for (int i = 0; i < n; i++) {
auto p = q.front();
q.pop();
// note we are doing -start because we don't need previous value
long long index = p.first - start;
TreeNode* curr = p.second;
if (curr->left) q.push({2 * index + 1, curr->left});
if (curr->right) q.push({2 * index + 2, curr->right});
}
ans = max(ans, end - start + 1);
}
return (int)ans;
}
/* QUESTION:
Given a Binary Tree. Return true if, for every node X in the tree other than the leaves, its value is equal to the sum of its left subtree's value and its right subtree's value. Else return false.
An empty tree is also a Sum Tree as the sum of an empty tree can be considered to be 0. A leaf node is also considered a Sum Tree.
Example 1:
Input:
3
/ \
1 2
Output: 1
Explanation:
The sum of left subtree and right subtree is 1 + 2 = 3, which is the value of the root node.
Therefore, the given binary tree is a sum tree.
APPROACH:
To determine if a binary tree is a Sum Tree, we can perform a post-order traversal of the tree and check if each node satisfies the condition of being a Sum Tree.
For each node in the tree, we will calculate the sum of its left subtree and right subtree. If both subtrees are Sum Trees and the value of the current node is equal to the sum of its subtrees, then the current node is also a Sum Tree. Otherwise, it is not a Sum Tree.
To indicate that the current node is not a Sum Tree, we return a special value (e.g., INT_MIN) from the recursive function. If the result is INT_MIN, then the binary tree is not a Sum Tree. Otherwise, it is a Sum Tree.
COMPLEXITY ANALYSIS:
Let `n` be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n) as we visit each node in the binary tree once during the post-order traversal.
- Space Complexity: The space complexity is O(h) due to the recursion stack, where h is the height of the binary tree.
CODE:
*/
int solve(Node* root) {
if (!root) return 0;
if (!root->left && !root->right) return root->data;
int lef = solve(root->left);
int rig = solve(root->right);
return (lef + rig == root->data) ? 2 * root->data : INT_MIN;
}
bool isSumTree(Node* root) {
int ans = solve(root);
return (ans == INT_MIN) ? false : true;
}
/* QUESTION:
Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.
You can return the answer in any order.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
APPROACH:
To find the nodes that are at a distance k from the target node, we can perform a two-step process:
1. First, traverse the binary tree to build a map of each node to its parent node using BFS. This map will help us later to backtrack from the target node to its ancestors.
2. Next, perform a BFS from the target node to find all nodes at a distance k from it. While doing this, we also mark visited nodes to avoid revisiting the same nodes.
COMPLEXITY ANALYSIS:
Let `n` be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n) since we need to traverse the entire binary tree to build the parent map and perform BFS from the target node.
- Space Complexity: The space complexity is O(n) for the parent map and O(k) for the queue used in BFS. In the worst case, when k approaches n, the space complexity becomes O(n).
CODE:
*/
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
vector<int> ans;
unordered_map<int, TreeNode*> parent;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int si = q.size();
for (int i = 0; i < si; i++) {
auto top = q.front();
q.pop();
if (top->left) {
parent[top->left->val] = top;
q.push(top->left);
}
if (top->right) {
parent[top->right->val] = top;
q.push(top->right);
}
}
}
unordered_map<int, int> visited;
q.push(target);
while (k-- && !q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
auto top = q.front();
q.pop();
visited[top->val] = 1;
if (top->left && !visited[top->left->val]) {
q.push(top->left);
}
if (top->right && !visited[top->right->val]) {
q.push(top->right);
}
if (parent[top->val] && !visited[parent[top->val]->val]) {
q.push(parent[top->val]);
}
}
}
while (!q.empty()) {
ans.push_back(q.front()->val);
q.pop();
}
return ans;
}
/* QUESTION:
Given a binary tree and a node data called target. Find the minimum time required to burn the complete binary tree if the target is set on fire. It is known that in 1 second, all nodes connected to a given node get burned. That is its left child, right child, and parent.
Note: The tree contains unique values.
Example 1:
Input:
1
/ \
2 3
/ \ \
4 5 6
/ \ \
7 8 9
\
10
Target Node = 8
Output: 7
Explanation: If the leaf with the value 8 is set on fire:
After 1 sec: 5 is set on fire.
After 2 sec: 2, 7 are set to fire.
After 3 sec: 4, 1 are set to fire.
After 4 sec: 3 is set to fire.
After 5 sec: 6 is set to fire.
After 6 sec: 9 is set to fire.
After 7 sec: 10 is set to fire.
It takes 7s to burn the complete tree.
APPROACH:
To find the minimum time required to burn the complete binary tree, we need to perform a BFS (level-order traversal) starting from the target node. While doing BFS, we will also keep track of the parent node for each node using a hash map. The parent node will be used to traverse upward from the target node in the BFS process.
We will burn the target node and its adjacent nodes (left child, right child, and parent) one by one in each second. By the time we burn all nodes in the last level, all other nodes in the binary tree would have been burned as well.
Finally, we will count the number of seconds it took to burn the complete binary tree.
COMPLEXITY ANALYSIS:
Let `n` be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n) since we perform a BFS starting from the target node, visiting all nodes in the binary tree once.
- Space Complexity: The space complexity is O(n) for the queue and the hash map.
CODE:
*/
void setParent(BinaryTreeNode<int>* root, unordered_map<BinaryTreeNode<int>*, BinaryTreeNode<int>*>& parent) {
if (!root) return;
if (root->data == start->data) s = root;
if (root->left) parent[root->left] = root;
if (root->right) parent[root->right] = root;
setParent(root->left, parent);
setParent(root->right, parent);
}
int timeToBurnTree(BinaryTreeNode<int>* root, BinaryTreeNode<int>* start) {
unordered_map<BinaryTreeNode<int>*, BinaryTreeNode<int>*> parent;
setParent(root, parent);
queue<BinaryTreeNode<int>*> q;
q.push(start);
int time = 0;
unordered_map<BinaryTreeNode<int>*, bool> vis;
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
auto curr = q.front();
q.pop();
if (curr->left && !vis[curr->left]) q.push(curr->left);
if (curr->right && !vis[curr->right]) q.push(curr->right);
if (parent[curr] && !vis[parent[curr]]) q.push(parent[curr]);
vis[curr] = true;
}
time++;
}
return time - 1;
}
/* QUESTION:
Given the root of a complete binary tree, return the number of nodes in the tree.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
APPROACH:
To count the number of nodes in the complete binary tree efficiently, we can make use of the property of complete binary trees. Since all levels of the tree, except possibly the last level, are completely filled, we can perform binary search on the last level to find the number of nodes.
1. First, we calculate the height of the left and right subtrees starting from the root.
2. If the height of the left subtree is equal to the height of the right subtree, it means that the last level is completely filled, and the number of nodes in the tree is 2^h - 1, where h is the height of the tree.
3. If the heights are not equal, it means that the last level is not completely filled. In this case, we recursively calculate the number of nodes in the left and right subtrees and add 1 (for the root node) to get the total number of nodes in the tree.
COMPLEXITY ANALYSIS:
Let n be the number of nodes in the complete binary tree.
- Time Complexity: The time complexity of this approach is O(log^2 n), as we perform binary search on the last level, and at each step, we calculate the height of the left and right subtrees, which takes O(log n) time. We do this operation recursively, so the overall time complexity is O(log^2 n).
- Space Complexity: The space complexity is O(log n) due to the recursion stack, where n is the height of the complete binary tree.
CODE:
*/
int leftHeight(TreeNode* root) {
int h = 1;
while (root) {
h++;
root = root->left;
}
return h;
}
int rightHeight(TreeNode* root) {
int h = 1;
while (root) {
h++;
root = root->right;
}
return h;
}
int countNodes(TreeNode* root) {
if (!root) return 0;
int lh = leftHeight(root->left);
int rh = rightHeight(root->right);
if (lh == rh)
return pow(2, lh) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}
/* QUESTION:
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.
APPROACH:
The preorder traversal follows the root-left-right order, while the inorder traversal follows the left-root-right order. Based on these two traversals, we can construct the binary tree recursively.
1. The first element in the preorder traversal array is the root of the binary tree.
2. We can find the position of the root in the inorder traversal array. All the elements to the left of this position will be in the left subtree, and all the elements to the right will be in the right subtree.
3. Recursively, we can build the left and right subtrees using the corresponding portions of the preorder and inorder traversal arrays.
4. The recursive function takes the index of the current element in the preorder traversal array, the starting and ending indices of the current portion in the inorder traversal array, and the preorder and inorder traversal arrays as inputs.
5. In each recursive call, we create a new node with the value of the current element in the preorder traversal array and determine its left and right subtrees by calling the recursive function on the corresponding portions of the inorder and preorder traversal arrays.
6. The base case is when the starting index is greater than the ending index, indicating an empty portion of the tree. In this case, we return NULL.
7. Finally, we return the root of the constructed binary tree.
COMPLEXITY ANALYSIS:
Let n be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n), as we visit each node once.
- Space Complexity: The space complexity is O(n) for the recursive call stack.
CODE:
*/
TreeNode* solve(int i, int ins, int ine, vector<int>& preorder, vector<int>& inorder) {
if (i >= preorder.size() || ins > ine) return NULL;
int loc = -1;
for (int j = ins; j <= ine; j++) {
if (inorder[j] == preorder[i])
loc = j;
}
TreeNode* root = new TreeNode(preorder[i]);
root->left = solve(i + 1, ins, loc - 1, preorder, inorder);
// Note: the index of the right child in preorder is the number of nodes in the left subtree + 1
root->right = solve(i + (loc - ins + 1), loc + 1, ine, preorder, inorder);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = inorder.size();
return solve(0, 0, n - 1, preorder, inorder);
}
/* QUESTION:
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
APPROACH:
The postorder traversal follows the left-right-root order, while the inorder traversal follows the left-root-right order. Based on these two traversals, we can construct the binary tree recursively.
1. The last element in the postorder traversal array is the root of the binary tree.
2. We can find the position of the root in the inorder traversal array. All the elements to the left of this position will be in the left subtree, and all the elements to the right will be in the right subtree.
3. Recursively, we can build the left and right subtrees using the corresponding portions of the inorder and postorder traversal arrays.
4. The recursive function takes the index of the current element in the postorder traversal array, the starting and ending indices of the current portion in the inorder traversal array, and the inorder and postorder traversal arrays as inputs.
5. In each recursive call, we create a new node with the value of the current element in the postorder traversal array and determine its left and right subtrees by calling the recursive function on the corresponding portions of the inorder and postorder traversal arrays.
6. The base case is when the starting index is greater than the ending index, indicating an empty portion of the tree. In this case, we return NULL.
7. Finally, we return the root of the constructed binary tree.
COMPLEXITY ANALYSIS:
Let n be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n), as we visit each node once.
- Space Complexity: The space complexity is O(n) for the recursive call stack.
CODE:
*/
TreeNode* solve(int pi, int ins, int ine, vector<int>& inorder, vector<int>& postorder) {
if (pi < 0 || ins > ine) return NULL;
int loc = -1;
for (int i = ins; i <= ine; i++) {
if (inorder[i] == postorder[pi])
loc = i;
}
TreeNode* root = new TreeNode(postorder[pi]);
root->right = solve(pi - 1, loc + 1, ine, inorder, postorder);
root->left = solve(pi - (ine - loc + 1), ins, loc - 1, inorder, postorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = inorder.size();
return solve(n - 1, 0, n - 1, inorder, postorder);
}
/* QUESTION:
Given a binary tree, find the preorder traversal of the tree without using extra space.
APPROACH:
We can achieve a non-recursive preorder traversal without using extra space by modifying the binary tree itself.
1. We start with the current node as the root.
2. While the current node is not NULL, we do the following:
- If the current node does not have a left child, we visit the current node and move to its right child.
- If the current node has a left child, we find the rightmost node of its left subtree.
- If the rightmost node does not have a right child, we visit the current node, make the right child of the rightmost node point to the current node, and move to the left child.
- If the rightmost node already has a right child (which points back to the current node), we reset the right child to NULL, visit the current node, and move to its right child.
3. We repeat this process until we have visited all the nodes in the tree.
4. Finally, we return the result vector containing the preorder traversal.
COMPLEXITY ANALYSIS:
Let n be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n) since we visit each node once.
- Space Complexity: The space complexity is O(1) since we don't use any extra space.
CODE:
*/
vector<int> preOrder(Node* root) {
vector<int> ans;
Node* curr = root;
while (curr) {
if (!curr->left) {
ans.push_back(curr->data);
curr = curr->right;
} else {
Node* rightmost = curr->left;
while (rightmost->right && rightmost->right != curr)
rightmost = rightmost->right;
if (!rightmost->right) {
ans.push_back(curr->data);
rightmost->right = curr;
curr = curr->left;
} else {
rightmost->right = NULL;
curr = curr->right;
}
}
}
return ans;
}
/* QUESTION:
Given a binary tree, find the inorder traversal of the tree without using extra space.
APPROACH:
We can achieve a non-recursive inorder traversal without using extra space by modifying the binary tree itself.
1. We start with the current node as the root.
2. While the current node is not NULL, we do the following:
- If the current node does not have a left child, we visit the current node and move to its right child.
- If the current node has a left child, we find the rightmost node of its left subtree.
- If the rightmost node does not have a right child, we make the right child point to the current node and move to the left child.
- If the rightmost node already has a right child (which points back to the current node), we reset the right child to NULL, visit the current node, and move to its right child.
3. We repeat this process until we have visited all the nodes in the tree.
4. Finally, we return the result vector containing the inorder traversal.
COMPLEXITY ANALYSIS:
Let n be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n) since we visit each node once.
- Space Complexity: The space complexity is O(1) since we don't use any extra space.
CODE:
*/
vector<int> inOrder(Node* root) {
vector<int> ans;
Node* curr = root;
while (curr) {
if (!curr->left) {
ans.push_back(curr->data);
curr = curr->right;
} else {
Node* rightmost = curr->left;
while (rightmost->right && rightmost->right != curr)
rightmost = rightmost->right;
if (!rightmost->right) {
rightmost->right = curr;
curr = curr->left;
} else {
ans.push_back(curr->data);
rightmost->right = NULL;
curr = curr->right;
}
}
}
return ans;
}
/* QUESTION:
Given the root of a binary tree, flatten the tree into a "linked list".
APPROACH:
To flatten the binary tree into a linked list, we can modify the tree in-place using a modified preorder traversal.
1. We start with the current node as the root.
2. While the current node is not NULL, we do the following:
- If the current node has a left child, we find the rightmost node of its left subtree.
- We make the right child of the rightmost node point to the right child of the current node.
- We set the left child of the current node to NULL.
- We set the right child of the current node to its left child.
- We move to the right child of the current node.
3. We repeat this process until we have visited all the nodes in the tree.
COMPLEXITY ANALYSIS:
Let n be the number of nodes in the binary tree.
- Time Complexity: The time complexity of this approach is O(n) since we visit each node once.
- Space Complexity: The space complexity is O(1) since we don't use any extra space.
CODE:
*/
void flatten(TreeNode* root) {
TreeNode* curr = root;
while (curr) {
if (curr->left) {
TreeNode* temp = curr->left;
while (temp->right)
temp = temp->right;
temp->right = curr->right;
curr->left = NULL;
curr->right = curr->left;
}
curr = curr->right;
}
}
/* QUESTION:
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
APPROACH:
To serialize the binary tree, we can perform a preorder traversal of the tree and append the node values to a string, separating them by a delimiter.
To deserialize the string back to the original tree structure, we can use a stringstream to split the string by the delimiter and recursively build the tree.
1. For serialization:
- If the current node is NULL, we append "N," to the string.
- Otherwise, we append the node value followed by a delimiter "," to the string.
- We then recursively serialize the left and right subtrees.
2. For deserialization:
- If the current string token is "N," indicating a NULL node, we return NULL.
- Otherwise, we convert the string token to an integer and create a new TreeNode with the value.
- We then recursively deserialize the left and right subtrees.
COMPLEXITY ANALYSIS:
Let n be the number of nodes in the binary tree.
- Time Complexity:
- Serialization: O(n) - We visit each node once during the serialization process.
- Deserialization: O(n) - We process each string token once during the deserialization process.
- Space Complexity: O(n) - The space required for the serialized string and the recursion stack.
CODE:
*/
void serialize(TreeNode* root, string& serialized) {
if (!root) {
serialized += "N,";
return;
}
serialized += to_string(root->val) + ",";
serialize(root->left, serialized);
serialize(root->right, serialized);
}
string serialize(TreeNode* root) {
string serialized;
serialize(root, serialized);
return serialized;
}
TreeNode* deserialize(stringstream& ss) {
string token;
getline(ss, token, ',');
if (token == "N")
return nullptr;
TreeNode* root = new TreeNode(stoi(token));
root->left = deserialize(ss);
root->right = deserialize(ss);
return root;
}
TreeNode* deserialize(string data) {
stringstream ss(data);
return deserialize(ss);
}