# Same Tree solution using TypeScript

This post outlines my TypeScript solution to the "Same Tree" question on LeetCode.

**Algorithm:**
This solution uses an iterative approach by pushing a StackNode containing two TreeNodes (one from each tree) to a Stack. StackNodes are then popped off the stack. For each one, check if both of the TreeNodes have equal values. If so, push pointers to the children of that node onto the stack. If they are not equal, return false.

**Time Complexity:**
Because each node in the tree will be visited once, the time complexity it * O(n)* where

*represents the number of nodes in the tree.*

**n****Space Complexity:**
Because the solution will push, at most, * 2 * H* pointers to the Stack where

*represents the height of the tree, the space complexity is*

**H***.*

**O(n)**```
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number,
* left?: TreeNode | null,
* right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
/**
* Same Tree
* 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.
*
* Time Complexity: O(n)
* Space Complexity: O(n)
*/
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
// create a stack to push tree nodes on to
const stack: StackNode[] = [[p, q]];
while (stack.length) {
const [a, b] = stack.pop() as StackNode;
// nodes match, push children to the stach
if (a && b && a.val === b.val) {
stack.push([a.left, b.left],
[a.right, b.right]);
}
// nodes do not match
else if (a || b) {
return false;
}
// nodes are both null, continue
}
return true;
}
// Represents a node on the Stack
type StackNode = [
TreeNode | null,
TreeNode | null
]
```