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.

Leaf-Similar Trees


  • Approach:

    1. The first step is to start from the root node of both trees. And traverse through the trees.

    2. While reaching the leaf node we will insert the value of the leaf node into a list.

    3. We will do this for both trees.

    4. So we will have two lists of leaf nodes coming out from two trees.

    5. Later we will return if both the list are equal or not.


  • Time and Space Complexity:

    • Time complexity: O(n) + Auxilary Stack

    • Space complexity: O(n)


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:


void traverse(TreeNode * root, vector<int> & ints){

if(root->left == NULL && root->right == NULL){

ints.push_back(root->val);

return;

}

if(root->left) traverse(root->left, ints);

if(root->right) traverse(root->right, ints);

}


bool leafSimilar(TreeNode* root1, TreeNode* root2) {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

vector<int>leaf_one, leaf_two;

traverse(root1, leaf_one);

traverse(root2, leaf_two);

return leaf_one == leaf_two;

}

};