Posts published in “Tree Traversal”

LeetCode 129. Sum Root to Leaf Numbers (javascript)

By stone on April 13, 2021

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers.

A leaf node is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 9
The depth of the tree will not exceed 10.

Idea:

Use DFS Template

Solution 1:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    if (root === null) return;
    let res = [];
    let cur = [];
    dfs(root, res, cur);
    let sum = 0;
    for (let num of res) {
        sum += num;
    }
    return sum;
};

function dfs(root, res, cur) {
    // exit recursion:
    if (root === null) return;
    // found leaf, save the number
    if (root.left === null && root.right === null) {
        cur.push(root.val);
        res.push(parseInt(cur.join('')));
        cur.pop();
        return;
    }
    
    // possible solution
    if (root !== null) {
        cur.push(root.val);
        dfs(root.left, res, cur);
        dfs(root.right, res, cur);
        cur.pop();
    }
    return;
}

Solution 2: (Version 2)

var sumNumbers = function(root) {
    if (root === null) return;
    let res = [0];
    let cur = [0];
    dfs(root, res, cur);
    return res[0];
};

function dfs(root, res, cur) {
    // exit recursion:
    if (root === null) return;
    // found leaf, save the number
    if (root.left === null && root.right === null) {
        cur[0] = cur[0] * 10 + root.val;
        res[0] += cur[0];
        cur[0] = (cur[0] - root.val) / 10;
        return;
    }
    
    // possible solution
    if (root !== null) {
        cur[0] = cur[0] * 10 + root.val;
        dfs(root.left, res, cur);
        dfs(root.right, res, cur);
        cur[0] = (cur[0] - root.val) / 10;
    }
    return;
}

LeetCode 112. Path Sum (javascript)

By stone on April 11, 2021

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false

Example 3:

Input: root = [1,2], targetSum = 0
Output: false

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Solution: (Recursion)

Time complexity: O(n)
Space complexity: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if (root === null) return false;
    if (root.val === targetSum && root.left === null && root.right === null) return true;
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
};

LeetCode 145. Binary Tree Postorder Traversal (javascript)

By stone on April 5, 2021

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

Input: root = [1,null,2]
Output: [2,1]

Constraints:

The number of the nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Idea:

Use two stacks:

1. Push root to first stack.
2. Loop while first stack is not empty
   2.1 Pop a node from first stack and push it to second stack(res[])
   2.2 Push left and right children of the popped node to first stack
3. Pop all elements from second stack(res.reverse())

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    let res = []; // use res as another stack
    // empty tree case:
    if (root === null) return res;
    let stack = [];
    
    // postorder visit: left, right, root
    stack.push(root);
    while (stack.length !== 0) { 
        let cur = stack.pop();
        // treat it as stack, store them in reverse order:
        // i.e root, left, right
        res.push(cur.val); 
        if (cur.left) stack.push(cur.left);
        if (cur.right) stack.push(cur.right);
    }
    
    // we can pop all elements one by one, or just reverse them
    return res.reverse();
};

LeetCode 144. Binary Tree Preorder Traversal (javascript)

By stone on April 5, 2021

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Idea:

Create an empty stack and push root node to stack
Do the following while stack is not empty:
1. Pop an item from the stack and store to result array
2. Push right child of a popped item to stack
3. Push left child of a popped item to stack

Right child is pushed first: The right child is pushed before the left child to make sure that the left subtree is processed first.

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    let res = [];
    // empty tree case:
    if (root === null) return res;
    let stack = [];
    
    // preorder visit: root -> left -> right
    // so the right child is pushed before the left child
    // to make sure that the left subtree is processed first.
    stack.push(root);
    while (stack.length !== 0) {
        let cur = stack.pop();
        res.push(cur.val);
        if (cur.right) stack.push(cur.right);
        if (cur.left) stack.push(cur.left);
    }
    return res;
};

LeetCode 110. Balanced Binary Tree (javascript)

By stone on April 5, 2021

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-10⁴ <= Node.val <= 10⁴

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    if (root === null) return true;
    const res = [true];
    height(root, res);
    return res[0];
};

function height(root, res) {
    if (root === null) return 0;
    const l = height(root.left, res);
    const r = height(root.right, res);
    if (Math.abs(l - r) > 1) res[0] = false;
    return Math.max(l, r) + 1;
}

LeetCode 102. Binary Tree Level Order Traversal (javascript)

By stone on April 4, 2021

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Idea:

Use BFS Template

Note: Don’t forget root === null case

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    const res = [];
    if (root === null) return res;
    
    const queue = [];
    queue.push(root);
    while(queue.length !== 0) {
        let size = queue.length;
        let level = []; // store same level nodes
        while(size--) {
            let cur = queue.shift();
            level.push(cur.val);
            if (cur.left) queue.push(cur.left);
            if (cur.right) queue.push(cur.right);
        }
        res.push(level.concat());
    }
    return res;
};

94. Binary Tree Inorder Traversal (javascript)

By stone on April 4, 2021

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [2,1]

Example 5:

Input: root = [1,null,2]
Output: [1,2]

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Idea:

Iterating method using Stack

Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let stack = [];
    let res = [];
    
    while(root !== null || stack.length !== 0) {
        while(root !== null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
}