Cognizant 2025 On Campus Hiring || Asked 2 Questions from Trees

They Asked me 2 Questions Related to trees

Q - 1 -> There is teacher in a school who have it's 2 favourite childrens. Both her students made a binary tree from same numbers but in diffrent format. The task for teacher is to view 1st student's tree from behind moving from left - right and noted down the numbers she sees. For 2nd student she moved from right - left and noted down the sequence. Now return true if both sequences are same otherwise false.

INTUTION ->

When someone looks a tree from bottom he / she can only sees the leaf nodes only.Soo we have to simply store the leaf nodes of both the trees from left - right direction, reverses the values for 2nd student nodes and then check if both the vectors are different or not.

CODE

class Solution {
    private:
        void func(TreeNode* root, vector<int>& vis) {
            if (!root)
                return;
            if (!root->left and !root->right)
                vis.push_back(root->val);
            func(root->left, vis);
            func(root->right, vis);
        }
    public:
        bool isEqual(TreeNode* root1, TreeNode* root2) {
            vector<int> first, second;
            func(root1, first);
            func(root2, second);
            reverse(second.begin(), second.end());
            for (int i = 0; i < first.size(); i++) {
                if (first[i] != second[i])
                    return false;
            }

            return true;
        }
}

Q - 2 -> Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references. A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

INTUTION

Basic Intution is to follow some kind of traversal tpe dfs (post order, inorder, preorder) and whenever a leaf node is encountered then only we know that path till now is completed and we have to back track now to previous nodes and when we are backtracking remove the last node so to avoid the conflictions between different paths

CODE

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(nullptr) {}
 * };
 */
class Solution {
    using pii = pair<int, int>;
    using vi = vector<int>;

private:
    void func(TreeNode* root, vector<vi>& ans, vi& path, int sum, int target) {
        if (!root)
            return;

        path.push_back(root->val);
        sum += root->val;
        if (!root->left and !root->right and sum == target)
            ans.push_back(path);

        func(root->left, ans, path, sum, target);
        func(root->right, ans, path, sum, target);
        path.pop_back();
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vi> ans;
        vi path;
        func(root, ans, path, 0, targetSum);
        return ans;
    }
};

The path vector is passed by reference because of the fact to avoid multiple cpoies made in every function call.