Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.
Two binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [4,7], q = [4,null,7]
Output: false
Example 3:
Input: p = [1,2,3], q = [1,3,2]
Output: false
Let's say a user save their note in unisala.
// A simpler version focusing on the tree-like nature
savedNote
├── title: "CS101"
├── content: "Arrays"
└── children
└── {subtitle: "Sorting"}
└── children
└── {content: "O(n^2)"}
currentNote
├── title: "CS101"
├── content: "Arrays"
└── children
└── {subtitle: "Sorting"}
└── children
└── {content: "O(n)"} // Changed here
The pattern from isSameTree - recursive comparison - helps efficiently check if a note actually needs saving:
Version Control for Notes
When a student has auto-save enabled, we need to quickly determine if their note has actually changed before saving a new version:
function hasNoteChanged(currentNote, savedNote) {
The Problem:
Students are typing/editing notes continuously
We don't want to save to the database every single second
We only want to save when actual changes have occurred
Notes are nested (sections within sections)
}
Why isSameTree's pattern is perfect here:
Early Exit: The moment it finds any difference between versions, it can immediately tell us i.e save is needed without checking the rest of the note
Deep Comparison: If a change happened in the deepest section, it can navigate through all the layers to find it
Memory Efficient: It only needs to look at each part of the note once
Simple Output: All we need to know is same or different - exactly what isSameTree tells us
// Usage
function autoSave(currentNote, savedNote) {
if (hasNoteChanged(currentNote, savedNote)) {
// Save new version to database
} else {
// Skip saving - notes are identical
}
}
How to develop the algorithm to check isSameTree(p,q)?
This algorithm is so intuitive:
We initialise a pointer and move it same direction in both the trees
if both node doesn't exist it is valid
if one exist and another doesn't it is invalid
if at any point the value is not equal then it is not the same binary tree
Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.
Two binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.
Example 1:
Example 2:
Example 3:
Let's say a user save their note in unisala.
// A simpler version focusing on the tree-like nature savedNote ├── title: "CS101" ├── content: "Arrays" └── children └── {subtitle: "Sorting"} └── children └── {content: "O(n^2)"}currentNote ├── title: "CS101" ├── content: "Arrays" └── children └── {subtitle: "Sorting"} └── children └── {content: "O(n)"} // Changed hereVersion Control for Notes
When a student has auto-save enabled, we need to quickly determine if their note has actually changed before saving a new version:
function hasNoteChanged(currentNote, savedNote) {The Problem:
Why isSameTree's pattern is perfect here:
// Usage function autoSave(currentNote, savedNote) { if (hasNoteChanged(currentNote, savedNote)) { // Save new version to database } else { // Skip saving - notes are identical } }This algorithm is so intuitive:
isSameTree(p, q){ if(!p && !q){ return true } if(!p || !q){ return false } if(p.val !== q.val){ return false } return this.isSameTree(p.left, q.left) && this.isSameTree(p.right, q.right) }