Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Inorder traversal is Left -> Root -> Right. So, we will call dfs recursively on the left node, push the value and do the same for the right child node. {: .prompt-tip }
void dfs(TreeNode* root, vector<int> &ans){
if(!root) return;
dfs(root->left, ans);
ans.push_back(root->val);
dfs(root->right, ans);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
dfs(root, ans);
return ans;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $
Core logic is exactly similar to the previous approach but in this method instead of calling a recursive helper function we will use stack data structure. {: .prompt-tip }
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
TreeNode* curr = root;
while (curr || !st.empty()) {
while (curr) {
st.push(curr);
curr = curr -> left;
}
curr = st.top();
st.pop();
ans.push_back(curr -> val);
curr = curr -> right;
}
return ans;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $
{: .prompt-tip }
Time Complexity: $ O(n) $
Auxiliary Space: $ O(1) $
Given the root of a binary tree, return the preorder traversal of its nodes’ values.
Preorder traversal is Root -> Left -> Right. So, we will push the value and call dfs recursively on the left node and the right child node. {: .prompt-tip }
void dfs(TreeNode* root, vector<int> &ans){
if(!root) return;
ans.push_back(root->val);
dfs(root->left, ans);
dfs(root->right, ans);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
dfs(root, ans);
return ans;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $
Core logic is exactly similar to the previous approach but in this method instead of calling a recursive helper function we will use stack data structure. Another important thing to note is we will first push right node and then the left node. It is due to the LIFO nature of stack. {: .prompt-tip }
vector<int> preorderTraversal(TreeNode* root) {
if(!root) return {};
vector<int> ans;
stack<TreeNode*> st;
TreeNode* curr;
st.push(root);
while(!st.empty()){
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;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $
{: .prompt-tip }
Time Complexity: $ O(n) $
Auxiliary Space: $ O(1) $
Given the root of a binary tree, return the Postorder traversal of its nodes’ values.
Postorder traversal is Left -> Right -> Root. So, we will call dfs recursively on the left node, the right child node and then push the value, {: .prompt-tip }
void dfs(TreeNode* root, vector<int> &ans){
if(!root) return;
dfs(root->left, ans);
dfs(root->right, ans);
ans.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
dfs(root, ans);
return ans;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $
Core logic is exactly similar to the previous approach but in this method instead of calling a recursive helper function we will use stack data structure. {: .prompt-tip }
vector<int> postorderTraversal(TreeNode* root) {
if(!root) return {};
vector<int> ans;
stack<TreeNode*> s;
TreeNode* last = NULL;
while(root || !s.empty()){
if(root){
s.push(root);
root = root->left;
}
else{
root = s.top();
if(root->right == NULL || root->right == last){
ans.push_back(root->val);
s.pop();
last = root;
root = NULL;
}
else root = root->right;
}
}
return ans;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $
{: .prompt-tip }
Time Complexity: $ O(n) $
Auxiliary Space: $ O(1) $
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.
Depth or height of the tree is number of node in path from root node to farthest leaf node. It can be assumed as the maximum height among left or right subtree incremented by 1. {: .prompt-tip }
int maxDepth(TreeNode* root) {
if(!root) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
This question can be broken down as to into three simple steps. First, calculate the height of left and right nodes, check for absolute difference and do the same for both the child subtrees. {: .prompt-tip }
int dfs(TreeNode* root){
if(!root) return 0;
return 1 + max(dfs(root->left), dfs(root->right));
}
bool isBalanced(TreeNode* root) {
if(!root) return true;
int left = dfs(root->left), right = dfs(root->right);
return abs(left-right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
Time Complexity: $ O(n^2) $
Auxiliary Space: $ O(n) $
It is similar to the previous approach but instead of returning the actual height of the child node, we just return -1 to mark that subtree as unbalanced. Thus we visit each node only once. {: .prompt-tip }
int dfs(TreeNode* root) {
if (!root) return 0;
int left = dfs(root->left), right = dfs(root->right);
return (left == -1 || right == -1 || abs(left-right) > 1) ? -1 : max(left, right)+1;
}
bool isBalanced(TreeNode* root) {
return dfs(root) != -1;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
This question can be broken down as to into three simple steps. First, calculate the height of left and right nodes, check for absolute difference and do the same for both the child subtrees. {: .prompt-tip }
int maxdiadepth = 0;
int dfs(TreeNode* root){
if(root == NULL) return 0;
int leftdepth = dfs(root->left);
int rightdepth = dfs(root->right);
if(leftdepth + rightdepth > maxdiadepth) maxdiadepth = leftdepth + rightdepth;
return max(leftdepth, rightdepth) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return maxdiadepth;
}
Time Complexity: $ O(n^2) $
Auxiliary Space: $ O(n) $
It is similar to the previous approach but instead of returning the actual height of the child node, we just return -1 to mark that subtree as unbalanced. Thus we visit each node only once. {: .prompt-tip }
int dfs(TreeNode* root) {
if (!root) return 0;
int left = dfs(root->left), right = dfs(root->right);
return (left == -1 || right == -1 || abs(left-right) > 1) ? -1 : max(left, right)+1;
}
bool isBalanced(TreeNode* root) {
return dfs(root) != -1;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $
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.
Return true if both p and q are null. Then check if either of them is null or not. Lastly, return false, if they differ in value. Apply the same for left and right child node. {: .prompt-tip }
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p and !q) return true;
if(!p or !q) return false;
if(p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
Time Complexity: $ O(n^2) $
Auxiliary Space: $ O(n) $
It is similar to the previous approach but instead of returning the actual height of the child node, we just return -1 to mark that subtree as unbalanced. Thus we visit each node only once. {: .prompt-tip }
bool isSameTree(TreeNode* p, TreeNode* q) {
queue<TreeNode*> qu;
TreeNode *n1, *n2;
qu.push(p);
qu.push(q);
while(qu.size() != 0){
n1 = qu.front();
qu.pop();
n2 = qu.front();
qu.pop();
if(!n1 && !n2) continue;
if(!n1 || !n2) return false;
if(n1->val != n2->val) return false;
qu.push(n1->left);
qu.push(n2->left);
qu.push(n1->right);
qu.push(n2->right);
}
return true;
}
Time Complexity: $ O(n) $
Auxiliary Space: $ O(n) $