hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Same Tree


  • Approach:

    1. Before accessing the nodes we need to use a Null Check. If both of them are NULL then return true.

    2. If one of them is NULL return false.

    3. If the value of both nodes is not equal return false.

    4. If the value of both nodes is equal and if the left and right nodes of both root nodes do not return false from any of the 3 above steps then we can return true.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(1) + Stack Usage


Code [C++]

/**

* 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(right) {}

* };

*/

class Solution {

public:

bool isSameTree(TreeNode* p, TreeNode* q) {

if(!p && !q) return true;

if((p && !q) || (!p && q) || (p->val != q->val)) return false;

return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

}

};