Depth First Search and Breadth First Search Algorithm in Checking Sum of Children Nodes in Binary Tree

Given a binary tree root, return whether for every node in the tree other than leaves, its value is equal to the sum of its left child’s value and its right child’s value.

For example, return true for

   9
  / \
 1   8
    / \
   6   2
  /
 6  

And return false for

   9
  / \
 1   3

Since 1 + 3 is not 9.

Example 1
Input
root = [10, [6, null, null], [4, null, null]]
Output
true

Checking the sum of children nodes (except leaf nodes) can be done by either using Breadth First Search Algorithm or Depth First Search Algorithm.

Checking the Sum of Children Nodes using DFS Algorithm

If it is leaf node or the current node is NULL, we simply do nothing and return. Otherwise, we compute the sum of its child(ren) node, and compare if it is the same as the current node. Also we need to recursively check its left tree and right tree to see if subtrees also satisfy the requirement.

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

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
bool solve(Tree* root) {
    if (root == NULL) return true;
    if (root->left == NULL && root->right == NULL) return true;
    int val = root->val;
    int other = 0;
    if (root->left != NULL) other += root->left->val;
    if (root->right != NULL) other += root->right->val;
    return (val == other) && solve(root->left) && solve(root->right);
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
bool solve(Tree* root) {
    if (root == NULL) return true;
    if (root->left == NULL && root->right == NULL) return true;
    int val = root->val;
    int other = 0;
    if (root->left != NULL) other += root->left->val;
    if (root->right != NULL) other += root->right->val;
    return (val == other) && solve(root->left) && solve(root->right);
}

The time complexity is O(N) where N is the number of nodes in the binary tree. The space requirement is O(N) due to the usage of a stack from Recursion.

Children Nodes Sum in Binary Tree using BFS Algorithm

On the other hand, we can implement a BFS algorithm that searches the tree level by leve. Then before we expand the children nodes, we check if the sum requirement satisfies. If it is a leaf node, we return false immediately.

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

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
bool solve(Tree* root) {
    if (!root) return true;
    queue<Tree*> Q;
    Q.push(root);
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        if (p->left || p->right) {
            int sum = 0;
            if (p->left) {
                sum += p->left->val;
                Q.push(p->left);
            }
            if (p->right) {
                sum += p->right->val;
                Q.push(p->right);
            }
            if (sum != p->val) return false;
        }
    }
    return true;
}

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
bool solve(Tree* root) {
    if (!root) return true;
    queue<Tree*> Q;
    Q.push(root);
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        if (p->left || p->right) {
            int sum = 0;
            if (p->left) {
                sum += p->left->val;
                Q.push(p->left);
            }
            if (p->right) {
                sum += p->right->val;
                Q.push(p->right);
            }
            if (sum != p->val) return false;
        }
    }
    return true;
}

This BFS Algorithm has a similar runtime complexity O(N) and the space requirement is also O(N).

See also (BFS): Teaching Kids Programming – Breadth First Search Algorithm to Determine Sum Binary Tree

Also the DFS version in Python: Teaching Kids Programming – Depth First Search Algorithm to Determine Sum Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —