Check if Two Trees are Identical
Medium Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Identical Binary Trees: Determining if Two Binary Trees are Identical, Binary Tree, Recursion, Tree Traversal, Time Complexity, Space Complexity, space complexity, node properties, binary tree, recursion base case, recursion, time complexity analysis, tree traversal, Check for Identical Trees.
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 values. Input Format: The input will be given as a level order traversal of the binary trees, where 1 denotes a null node. For example, a tree 1 2 3 1 1 4 5 represents: Output Format: Return true if the two trees are identical, otherwise return false. Examples: Example 1: Input: Binary Tree 1: 1 2 3 1 1 4 5 Binary Tree 2: 1 2 3 1 1 4 5 Output: true Explanation: Two trees are said to be identical if these three conditions are met for every pair of nodes: 1. Value of a node in the first tree is equal to the value of the corresponding node in the second tree. 2. Left subtree of this node is identical to the left subtree of the corresponding node. 3. Right subtree of this node is identical to the right subtree of the corresponding node. Example 2: Input: Binary Tree 1: 1 2 3 1 1 4 5 Binary Tree 2: 1 2 3 1 1 4 Output: false Explanation: The two binary trees are not identical because they fail to satisfy the third condition for every pair of nodes. Specifically, the right subtree of the corresponding nodes in the two trees is not identical. In Binary Tree 1, the node with value 3 has a right subtree with nodes 4 and 5. However, in Binary Tree 2, the corresponding node with value 3 has a right subtree with only the node 4. Since the right subtrees are not the same, the two trees are not identical according to the given conditions.