# Symmetric Tree solution using TypeScript

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

Algorithm: This solution uses an iterative approach by pushing a StackNode containing two TreeNodes (one for each child) 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 n represents the number of nodes in the tree.

Space Complexity: Because the solution will push, at most, 2 * H pointers to the Stack where H represents the height of the tree, the space complexity is 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)
*     }
* }
*/

/**
* Symmetric Tree
* Given a binary tree, check whether it is a mirror
* of itself (ie, symmetric around its center).
*
* This binary tree [1,2,2,3,4,4,3] is symmetric:
*     1
*    / \
*   2   2
*  / \ / \
* 3  4 4  3
*
* This tree [1,2,2,null,3,null,3] is not:
*     1
*    / \
*   2   2
*    \   \
*     3    3
*
* Time Complexity: O(n)
* Space Complexity: O(n)
*/
function isSymmetric(root: TreeNode | null): boolean {
if (!root) {
return true;
}

// create a stack to compare the children
const stack: StackNode[] = [
[root.left, root.right]
];

while (stack.length) {
const [a, b] = stack.pop() as StackNode;
// nodes match, push their children to the stack
if (a && b && a.val == b.val) {
stack.push([a.left, b.right],
[a.right, b.left])
}
// 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
]
``````