Posts published in “Tree Traversal”

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.

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;
}``````

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`.

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);
};``````

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();
};``````

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;
};``````

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]`.
• `-104 <= Node.val <= 104`

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;
}``````

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;
};``````

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;
}``````