DAY 58 - Binary Tree Questions(II)

Welcome to DAY 58. Today we will diverge once again into the Data Structure Trees and look at some more traversals. I suggest reading the previous articles that I have written on Trees before reading this.

Question 1: 101. Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

• Input: root = [1,2,2,3,4,4,3]
• Output: true

Intuition:

• The question is pretty simple and easy.
• We start from the root node and go to it's left and right subtree's we check if the are equal.
• We use recursion to follow the same process and if they are we return true else we return false.

Algorithm & Code:

Algorithm:

• We create a new function inside the same class to help us travel recursively in this tree.
• We initialize the base case if one root is null or if both are null we return true only when both are null otherwise we return false as they can't be identical.
• We check if the value of both the roots is equal and if root1's left and root2's right is equal and root2's left and root1's right is equal.
• This will make it symmetric up until that point in those subtrees.
• We call the same function in the main function and get the answer.

Code:

class Solution {
public:
    bool isSymmetricUtil(TreeNode* root1, TreeNode* root2){
        if(root1 == NULL || root2 == NULL){
            return root1 == root2;
        }
        return root1->val == root2->val && isSymmetricUtil(root1->left,root2->right) && isSymmetricUtil(root2->left,root1->right);
    }
    bool isSymmetric(TreeNode* root) {
        return isSymmetricUtil(root->left, root->right);
    }
};

Complexity Analysis:

• Time: O(N)
• Space: O(N) recursion stack

Question 2: Binary Tree Right Side View

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.

_Example: _

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

Intuition:

• So basically we need to find out the rightmost thing on that level.
• So what we can do is check the right subtree first and if there are none we go left.
• This way we can have our priorities from right to left and ultimately lead to a correct answer.
• We also need to maintain a level counter and if we enter a new level, we simply increase the levels and add that specific node which we encountered into our answer.

Algorithm and Code:

*Algorithm: *

• The helper function takes three parameters: the current node (root), the level of the current node (level), and the result vector (res) that will store the right side view.
• If the current node is nullptr (i.e., there is no node), the function returns without any further processing.
• If the size of the result vector (res) is equal to the current level, it means that this is the first node encountered at this level from the right side. In this case, the function appends the current node's value to the result vector.
• The helper function then recursively calls itself on the right child of the current node with the level incremented by 1.
• Next, the helper function recursively calls itself on the left child of the current node with the level incremented by 1. This ensures that the rightmost node at each level is added to the result vector.

Code:

 */
class Solution {
public:
    void helper(TreeNode* root, int level, vector<int> & res){
        if(root == nullptr) return ;
        if(res.size() == level) res.push_back(root->val);
        helper(root->right,level+1,res);
        helper(root->left,level+1,res);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        helper(root,0,ans);
        return ans;
    }
};

Complexity Analysis:

• Time: O(N)
• Space: O(Height)