Invert Binary Tree solution using TypeScript

leetcode

Below is my TypeScript solution to the LeetCode "Invert Binary Tree" question using a recursive approach.

Because each node will be visited one time, the time complexity is O(n), where n represents the number of nodes in the tree.

This approach will place O(h) function calls on the stack in the worst case, where h is the height of the tree. This makes the space complexity 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)
 *     }
 * }
 */

/**
 * Inverts a Binary Tree using a recursive approach.
 *
 *   Time Complexity: O(n) 
 *   Space Complexity: O(n)
 *
 *   Input: 4          Output: 4
 *        /   \              /   \
 *       2     7            7     2
 *      / \   / \          / \   / \
 *     1   3 6   9        9   6 3   1  
 */
function invertTree(root: TreeNode | null): TreeNode | null {
    if (isTreeNode(root)) {
        const left = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = left;
    }
    return root;
}

/**
 * Type Guard for validating that a value is of type TreeNode.
 * Does not rely on constructor name as the name could be minified.
 * 
 *   Time Complexity: O(1)
 *   Space Complexity: O(1)
 */ 
function isTreeNode(root: any): root is TreeNode {
    return root !== null 
        && typeof root === 'object'
        && typeof root.val === 'number'
        && typeof root.left === 'object'
        && typeof root.right === 'object'
}

more LeetCode posts