Same Tree
You are given two binary trees. Return true when they are exactly the same : the same shape, with the same number stored at every matching position. Return false otherwise. Both trees arrive as level-order arrays , for example p = [1, 2, 3] and q = [1, 2, 3], with null marking a missing child. Your function builds both trees and returns true or false. No tree object is passed in or out. Walk both trees in step with each other . At every position ask three questions: are both nodes missing, is exactly one missing, and do the two numbers differ? Those three answers decide everything.
Constraints
- Each tree has between 0 and 100 nodes
- -104 ≤ node value ≤ 104
- Both inputs are level-order arrays with null for a missing child
- Return a boolean
Example
p = [1, 2, 3], q = [1, 2, 3]trueExplanation Both trees have a root holding 1, a left child holding 2 and a right child holding 3. Every matching position agrees, so the answer is true.
In plain terms
- Node
- One box in the tree. It holds a number and two links, one to a left child and one to a right child. A link can be empty, written as null.
- Leaf
- A node with no children at all: both its left and right links are empty.
- Base case
- The simple situation where a self-calling function stops calling itself and answers directly. Here, running off the bottom of both trees at once is a base case, and the answer is true.
One cell per matching position, showing the pair of values compared there
Both trees are built and we stand at the root of each.
What happens in this step
p = [1, 2, 3] q = [1, 2, 3] a = root of p, b = root of q No position has been compared yet.
Steps to visualize
- Each cell is a position visited in both trees at the same time.
- The cell fills in with the two values found there once that position has been checked.
- If the two values ever differ, or one tree has a node where the other has nothing, the answer is false straight away.
- If every position agrees and both trees run out together, the answer is true.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Both trees are built and we stand at the root of each.
What happens in this step
p = [1, 2, 3] q = [1, 2, 3] a = root of p, b = root of q No position has been compared yet.
Solution
function isSameTree(p, q) {
function Node(value) {
this.val = value;
this.left = null;
this.right = null;
}
function buildTree(list) {
if (list.length === 0 || list[0] === null) {
return null;
}
const root = new Node(list[0]);
const queue = [root];
let i = 1;
while (i < list.length && queue.length > 0) {
const node = queue.shift();
if (list[i] !== null && list[i] !== undefined) {
node.left = new Node(list[i]);
queue.push(node.left);
}
i += 1;
if (list[i] !== null && list[i] !== undefined) {
node.right = new Node(list[i]);
queue.push(node.right);
}
i += 1;
}
return root;
}
function same(a, b) {
if (a === null && b === null) {
return true;
}
if (a === null || b === null) {
return false;
}
if (a.val !== b.val) {
return false;
}
return same(a.left, b.left) && same(a.right, b.right);
}
return same(buildTree(p), buildTree(q));
}- Time
- O(n)
- Space
- O(h)
Test cases
| Input | Expected | Covers |
|---|---|---|
p = [1, 2, 3], q = [1, 2, 3] | true | example from the docstring |
p = [1, 2], q = [1, null, 2] | false | same values but mirrored shape |
p = [1, 2, 1], q = [1, 1, 2] | false | same shape but the values are swapped |
p = [], q = [] | true | two empty trees are the same |
p = [1], q = [] | false | one tree is empty and the other is not |
p = [1, 2, 3, 4, 5], q = [1, 2, 3, 4, 5] | true | a larger identical pair |