🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we'll explore a fundamental problem in binary tree data structures - determining if two binary trees are identical. This problem is known as the "Identical Binary Trees" or "Same Tree" problem and is a common question in coding interviews to assess understanding of tree traversal and comparison in Java.
Problem
Given two binary trees, 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 value.
Example 1:
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:
Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: false
Example 3:
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
2. Solution Steps
1. If both trees are null, return true.
2. If one of the trees is null or the values of the root nodes are not equal, return false.
3. Recursively check if the left subtree of the first tree is identical to the left subtree of the second tree and the right subtree of the first tree is identical to the right subtree of the second tree.
4. Return the result of the recursive checks.
3. Code Program
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
// Main method for testing
public static void main(String[] args) {
TreeNode tree1 = new TreeNode(1);
tree1.left = new TreeNode(2);
tree1.right = new TreeNode(3);
TreeNode tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(3);
System.out.println("Are trees identical: " + isSameTree(tree1, tree2));
}
// Method to check if two binary trees are the same
public static boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true; // Both trees are null
if (p == null || q == null) return false; // One of the trees is null
if (p.val != q.val) return false; // Values of nodes are not equal
// Recursively check left and right subtrees
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
Output:
Are trees identical: true
Explanation:
In the example, both trees have the same structure and node values (1 -> 2 -> 3).
The method isSameTree checks if both trees are null, indicating they are identical. If only one is null or the root values are different, it returns false.
Otherwise, it recursively checks the left and right subtrees for equality. The result is true, indicating the trees are identical.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment