LeetCode - Tree

Posted on | In ,

Record the Tree topic algorithm problems.

0094. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.
Example:
Input: [1,null,2,3]
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

solution 1:

1
2
3
4
5
6
7
8
const inorderTraversal = (root, arr = []) => {
    if (root) {
        inorderTraversal(root.left, arr);
        arr.push(root.val);
        inorderTraversal(root.right, arr);
    }
    return arr;
};

Runtime: 52 ms
Memory Usage: 33.9 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const inorderTraversal = (root) => {
    const stack = [];
    const res = [];
    while (root || stack.length) {
        if (root) {
            stack.push(root);
            root = root.left;
        } else {
            root = stack.pop();
            res.push(root.val);
            root = root.right;
        }
    }

    return res;
};

Runtime: 48 ms
Memory Usage: 33.9 MB

0098. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:
Input: [2,1,3]
Output: true
Example 2:
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node’s value is 5 but its right child’s value is 4.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const isValidBST = (root) => {
    if (!root) {
        return true;
    }

    function helper(root, min, max) {
        if (!root) {
            return true;
        }

        if ((min !== null && root.val <= min) || (max !== null && root.val >= max)) {
            return false;
        }

        // Continue to scan left and right
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }

    return helper(root, null, null);
};

Runtime: 64 ms
Memory Usage: 37.6 MB

0101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric
But the following [1,2,2,null,3,null,3] is not

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
Definition for a binary tree node.
function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}
@param {TreeNode} root
@return {boolean}
*/
const isSymmetric = (root) => {
if (!root) { // Sanity check
return true;
}

    // Check if tree s & t are mirroring each other
    function isMirror(s, t) {
        if (!s && !t) {
            return true; // Both nodes are null, ok
        }
        if (!s || !t || s.val !== t.val) {
            return false; // Found a mismatch
        }
        // Compare the left subtree of `s` with the right subtree of `t`
        // and the right subtree of `s` with the left subtree of `t`
        return isMirror(s.left, t.right) && isMirror(s.right, t.left);
    }

    return isMirror(root.left, root.right);

};

Time complexity is O(n), and space complexity is O(1)
Runtime: 64 ms
Memory Usage: 35.6 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

const isSymmetric = (root) => {
if (!root) { // Sanity check
return true;
}

    // Check if tree s & t are mirroring each other
    function isMirror(p, q) {
        // Create two stacks
        var s1 = [p], s2 = [q];

        // Perform preorder traversal
        while (s1.length > 0 || s2.length > 0) {
            var n1 = s1.pop(), n2 = s2.pop();

            // Two null nodes, let's continue
            if (!n1 && !n2) continue;

            // Return false as long as there is a mismatch
            if (!n1 || !n2 || n1.val !== n2.val) return false;

            // Scan tree s from left to right
            // and scan tree t from right to left
            s1.push(n1.left); s1.push(n1.right);
            s2.push(n2.right); s2.push(n2.left);
        }

        return true;
    }

    return isMirror(root.left, root.right);

};

Time complexity is still O(n), and space complexity is the height of the tree.
Runtime: 64 ms
Memory Usage: 35.5 MB

solution 3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

const isSymmetric = (root) => {
if (!root) { // Sanity check
return true;
}

    // Check if tree s & t are mirroring each other
    function isMirror(s, t) {
        let q1 = [s], q2 = [t];

        // Perform breadth-first search
        while (q1.length > 0 || q2.length > 0) {
            // Dequeue
            let n1 = q1.shift(), n2 = q2.shift();

            // Two null nodes, let's continue
            if (!n1 && !n2) {
                continue;
            }

            // Return false as long as there is a mismatch
            if (!n1 || !n2 || n1.val !== n2.val) {
                return false;
            }

            // Scan tree s from left to right
            // and scan tree t from right to left
            q1.push(n1.left); q1.push(n1.right);
            q2.push(n2.right); q2.push(n2.left);
        }

        return true;
    }

    return isMirror(root.left, root.right);

};

Time complexity is O(n) and space complexity is the width of the tree.
Runtime: 68 ms
Memory Usage: 35.6 MB

0102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const levelOrder = (root) => {
    if (!root) {
        return [];
    }
    const stack = [];
    stack.push(root);
    const result = [];
    while (stack.length > 0) {
        const size = stack.length;
        const temp = [];
        for (let i = 0; i < size; i++) {
            const node = stack.shift();
            temp.push(node.val);
            if (node.left) {
                stack.push(node.left);
            }
            if (node.right) {
                stack.push(node.right);
            }
        }
        result.push(temp);
    }
    return result;
};

Runtime: 60 ms
Memory Usage: 35 MB

0104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
return its depth = 3.

solution:

1
2
3
4
5
6
7

const maxDepth = (root) => {
if (root === null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

Runtime: 52 ms
Memory Usage: 37.3 MB

0105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
[3,9,20,null,null,15,7]

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const buildTree = (preorder, inorder) => {
    let p = 0, i = 0;
    function build(stop) {
        if (inorder[i] !== stop) {
            let root = new TreeNode(preorder[p++])
            root.left = build(root.val)
            i++
            root.right = build(stop)
            return root
        }
        return null
    }
    return build()
};

Runtime: 80 ms
Memory Usage: 36.2 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const buildTree = (preorder, inorder) => {
    function helper(p1, p2, i1, i2) {
        if (p1 > p2 || i1 > i2) {
            return null;
        }
        let value = preorder[p1],           // get the root value
            index = inorder.indexOf(value), // get inorder position
            nLeft = index - i1,             // count nodes in left subtree
            root  = new TreeNode(value);    // build the root node

        // build the left and right subtrees recursively
        root.left  = helper(p1 + 1, p1 + nLeft, i1, index - 1);
        root.right = helper(p1 + nLeft + 1, p2, index + 1, i2);

        return root;
    }

    return helper(0, preorder.length - 1, 0, inorder.length - 1);
};

Runtime: 64 ms
Memory Usage: 36.3 MB

0108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5]

solution:

1
2
3
4
5
6
7
8
9
10
const sortedArrayToBST = (nums) => {
    if(!nums.length) {
        return null;
    }
    let mid = Math.floor((nums.length)/2);
    let root = new TreeNode(nums[mid]);
    root.left = sortedArrayToBST(nums.slice(0, mid));
    root.right = sortedArrayToBST(nums.slice(mid+1));
    return root;
};

Runtime: 72 ms
Memory Usage: 37.6 MB

0114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
[1,2,5,3,4,null,6]
The flattened tree should look like:
[1,null,2,null,3,null,4,null,5,null,6]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const flatten = (root) => {
    if (!root) {
        return;
    }
    let left = root.left;
    let right = root.right;
    flatten(left);
    flatten(right);
    root.left = null;
    root.right = left;
    let cur = root;
    while (cur.right !== null) {
        cur = cur.right;
    }
    cur.right = right;
};

Runtime: 60 ms
Memory Usage: 35.8 MB

0124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any node sequence from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:
Input: root = [1,2,3]
Output: 6

Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42

Constraints:
The number of nodes in the tree is in the range [0, 3 * 104].
-1000 <= Node.val <= 1000

solution1:

1
2
3
4
5
6
7
8
9
10
11
12
const maxPathSum = (root) => {
  let max = -Number.MAX_VALUE;
  getMaxSum(root);
  return max;
  function getMaxSum(node) {
    if (!node) return 0;
    const leftSum = getMaxSum(node.left);
    const rightSum = getMaxSum(node.right);
    max = Math.max(max, node.val + leftSum + rightSum);
    return Math.max(0, node.val + leftSum, node.val + rightSum);
  }
};

Runtime: 96 ms
Memory Usage: 48.3 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
const maxPathSum = (root) => {
  let max = -Infinity // Initialize to a very small number to handle a path of negative values
  getMaxSum(root) // Call our recursive fn to start the program
  return max // Once we have popped out of our recursive calls, `max` contains our maximum path sum
  function getMaxSum(tree) {
    if (tree == null) { return 0 } // Termination condition    
    const leftBranch = Math.max(0, getMaxSum(tree.left)) // calculate the root to leaf sum where root is the left node
    const rightBranch = Math.max(0, getMaxSum(tree.right)) // calculate the root to leaf sum where root is the right node
    const currentPath = leftBranch + tree.val + rightBranch  // Sum the path: left -> root -> right (leaf to leaf)   
    max = Math.max(max, currentPath) // if the current path is greater than the previous value of `max`, update `max` to the current path sum
    return tree.val + Math.max(leftBranch, rightBranch)
  }
};

Runtime: 100 ms
Memory Usage: 48.2 MB

0226. Invert Binary Tree

Example:
Input:
[4,2,7,1,3,6,9]
Output:
[4,7,2,9,6,3,1]

solution 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/\*\*

- Definition for a binary tree node.
- function TreeNode(val) {
-     this.val = val;
-     this.left = this.right = null;
- }
  \*/
  /\*\*
- @param {TreeNode} root
- @return {TreeNode}
  \*/
  // Recursive
  const invertTree = (root) => {
  if (root) {
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  }
  return root;
  };

Runtime: 60 ms
Memory Usage: 33.9 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// BFS
const invertTree = (root) => {
if (!root) {
return null;
}
let queue = [root];

    while (queue.length > 0) {

        const node = queue.shift();

        [node.left, node.right] = [node.right, node.left];

        if (node.left) {
            queue.push(node.left);
        }
        if (node.right) {
            queue.push(node.right);
        }
    }

    return root;

};

Runtime: 56 ms
Memory Usage: 33.8 MB

solution 3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// DFS
const invertTree = (root) => {
if (!root) {
return null;
}
let stack = [root];

    while (stack.length > 0) {

        const node = stack.pop();

        [node.left, node.right] = [node.right, node.left];

        if (node.left) {
            stack.push(node.left);
        }
        if (node.right) {
            stack.push(node.right);
        }
    }

    return root;

};

Runtime: 56 ms
Memory Usage: 33.8 MB

0230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Example 1:
Input: root = [3,1,4,null,2], k = 1
3
/
1 4

2
Output: 1

Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/
3 6
/
2 4
/
1
Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Constraints:
The number of elements of the BST is between 1 to 10^4.
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const kthSmallest = (root, k) => {
    if(root== null) return null;   
    let mini = 0;
    let stack = [];
    let temp ;
    while (true) {
        if (root!== null) {
            stack.push(root);
            root = root.left;
        } else {
            mini += 1;
            if (mini === k && stack.length !== 0) return stack[stack.length-1].val;
            else temp = stack.pop();
            root = temp.right; 
        }
    }
};

Runtime: 84 ms
Memory Usage: 44.2 MB

0236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

solution 1:

1
2
3
4
5
6
7
8
const lowestCommonAncestor = (root, p, q) => {
  if (!root || root === p || root === q) {
      return root;
  }
  let resL = lowestCommonAncestor(root.left, p, q);
  let resR = lowestCommonAncestor(root.right, p, q);
  return (resL && resR) ? root : (resL || resR);
};

Runtime: 88 ms
Memory Usage: 41.5 MB

solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
const lowestCommonAncestor = (root, p, q) => {
    if (!root || root === p || root === q) return root
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
    if (!left) {
        return right;  // p and q are in the right subtree
    }
    if (!right) {
        return left;  // p and q are in the left subtree
    }
    return root;     // p is in one side and q is in the other
};

Runtime: 64 ms
Memory Usage: 41.6 MB

0297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

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

Example 2:
Input: root = []
Output: []

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

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

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

solution1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const serialize = (root) => {
    let string = '';
    function buildString(node) {
        if (!node) {
            string += 'e ';
        } else {
            string += node.val + ' ';
            buildString(node.left);
            buildString(node.right);
        }
    }
    buildString(root);
    return string;
};

const deserialize = (data) => {
    let nodes = data.split(' ');
    function buildTree() {
        let val = nodes.shift();
        if (val === 'e') {
            return null;
        } else {
            let node = new TreeNode(Number(val));
            node.left = buildTree();
            node.right = buildTree();
            return node;
        }
    }
    return buildTree();
};

Runtime: 164 ms
Memory Usage: 49.3 MB

solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const serialize = (root) => {
    if (root === null) {
        return '';
    }
    const result = [];
    const queue = [root];    
    while (queue.length > 0) {
        const node = queue.shift();     
        if (node === null) {
            result.push('null');
            continue;
        }
        result.push(node.val);
        queue.push(node.left);
        queue.push(node.right);
    }
    
    // Remove the trailing nulls
    loop: for (let i=result.length - 1; i >= 0 ; i--) {
        if (result[i] === 'null') {
            result.splice(i, 1);
        } else {
            break loop;
        }
    }    
    return result.toString();
};

const deserialize = (data) => {
   if (data === '') {
        return null;
    }
    const values = data.split(',');
    const root = new TreeNode(parseInt(values[0]));
    const queue = [root];
    for (let i=1; i < values.length; i++) {
        const parent = queue.shift();        
        if (values[i] !== 'null') {
            const left = new TreeNode(parseInt(values[i]));
            parent.left  = left;
            queue.push(left);
        }
        if (values[++i] !== 'null' && i !== values.length) {
            const right = new TreeNode(parseInt(values[i]));
            parent.right = right;
            queue.push(right);
        }
    }  
    return root; 
};

Runtime: 128 ms
Memory Usage: 49.8 MB

0337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
Input: [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const rob = (root) => {
  const { current, next } = traverse(root);
  function traverse(root) {
      if (!root) {
        return { current: 0, next: 0 };
      }

      const left = traverse(root.left);
      const right = traverse(root.right);
      const current = root.val + left.next + right.next;
      const next = Math.max(left.current, left.next) + Math.max(right.current, right.next);

      return { current, next };
  }
  return Math.max(current, next);
};

Runtime: 68 ms
Memory Usage: 38.2 MB

0437. Path Sum III

You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
Return 3. The paths that sum to 8 are:

  1. 5 -> 3
  2. 5 -> 2 -> 1
  3. -3 -> 11

solution:

1
2
3
4
5
6
7
8
9
10
11
const pathSum = (root, sum, presums = { '0': 1 }, prev = 0) => {
    if (!root) {
        return 0;
    }
    let curr = prev + root.val;
    presums[curr] = (presums[curr] || 0) + 1;
    let res = (presums[curr - sum] || 0) - !sum;
    res += pathSum(root.left, sum, presums, curr) + pathSum(root.right, sum, presums, curr);
    presums[curr]--;
    return res;
};

Runtime: 68 ms
Memory Usage: 38.4 MB

0543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Given a binary tree [1,2,3,4,5]
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const diameterOfBinaryTree = (root) => {
    let diameter = 0;

    dfs(root);

    return diameter;

    function dfs(node, level) {
        if (!node) {
            return 0;
        }

        const left = dfs(node.left);
        const right = dfs(node.right);

        // update diameter at every node
        diameter = Math.max(diameter, left + right);

        // update the largest number of edge so far
        return 1 + Math.max(left, right);
    }
};

Runtime: 68 ms
Memory Usage: 37.1 MB

0617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:
Input
[1,3,2,5][2,1,3,null,4,null,7]
Output
[3,4,5,5,4,null,7]

solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const mergeTrees = (t1, t2) => {
    if (!t1 && !t2) {
        return null;
    }

    if (!t1 || !t2) {
        return t1 || t2;
    }

    var root = new TreeNode(t1.val + t2.val);

    root.left = mergeTrees(t1.left, t2.left);
    root.right = mergeTrees(t1.right, t2.right);

    return root;
};

Runtime: 92 ms
Memory Usage: 40.6 MB