Recursive Depth First Search Algorithm to Diagonal Tree Traversal

Given a binary tree root, return the sum of each of the diagonals in the tree starting from the top to bottom right. For example, given

   1
  / \
 4   2
    / \
   5   3
  / \
 7   6

Return [6, 15, 7] since the diagonals are:

1 – 2 – 3
4 – 5 – 6
7

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

Diagonal Tree Traversal via DFS

We observe that the level of diagonals can be counted as the number of left turns. Thus, we can do a Depth First Search algorithm and pass from top to down the number of left turns. And we accumulate the sum for each diagonals (the number of left turns).

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

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
vector<int> solve(Tree* root) {
    vector<int> res;
    function<void(Tree*, int)> dfs = [&](Tree* root, int left) {
        if (!root) return;
        if (left >= res.size()) {
            res.resize(res.size() + 1);
        }
        res[left] += root->val;
        dfs(root->left, left + 1);
        dfs(root->right, left);
    };
    dfs(root, 0);
    return res;
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
vector<int> solve(Tree* root) {
    vector<int> res;
    function<void(Tree*, int)> dfs = [&](Tree* root, int left) {
        if (!root) return;
        if (left >= res.size()) {
            res.resize(res.size() + 1);
        }
        res[left] += root->val;
        dfs(root->left, left + 1);
        dfs(root->right, left);
    };
    dfs(root, 0);
    return res;
}

The above DFS has been defined as a local lambda function via C++ functional. The complexity is O(N) where N is the number of the Tree Nodes. And the space complexity is also O(N) due to the implicit usage of stack from Recursion.

–EOF (The Ultimate Computing & Technology Blog) —