Check for children sum property in a Binary Tree

As an Input We are Given a tree and we have to check for children sum property. Whether that property if followed in an entire tree or not.

Note:- Deviation of even single Node from above property will result in a negative answer.

Children-Sum Property:-This property says that for each node sum of its left and right children should be equal to node value.

Also, following assumptions are to be kept in mind while recursively traversing tree

  1. A leaf node satisfies children sum property because leaf nodes don’t have any child nodes.
  2. An Empty tree satisfies Children sum property.

 

Algorithm:-

Step1:- Traverse the tree.
Step 2:- For every node in tree check whether the value in root node equals the sum of it lchild and rchild.

If yes continue from Step 1 Untill root==NULL

If No return false

The time complexity for above program is O(n). Since each node is covered once.

The code is –

class Node {
    int data;
    Node left, right;

    public Node(int d) {
        data = d;
        left = right = null;
    }
}

class BinaryTree {
    Node root;

    /* returns 1 if children sum property holds for the given
    node and both of its children*/
    int isSumProperty(Node node) {

        /* left_data is left child data and right_data is for right
           child data*/
        int left_data = 0, right_data = 0;

        /* If node is NULL or it's a leaf node then
        return true */
        if (node == null ||
            (node.left == null && node.right == null))
            return 1;
        else {

            /* If left child is not present then 0 is used
               as data of left child */
            if (node.left != null)
                left_data = node.left.data;

            /* If right child is not present then 0 is used
               as data of right child */
            if (node.right != null)
                right_data = node.right.data;

            /* if the node and both of its children satisfy the
               property return 1 else 0*/
            if ((node.data == left_data + right_data) &&
                (isSumProperty(node.left) != 0) &&
                isSumProperty(node.right) != 0)
                return 1;
            else
                return 0;
        }
    }

    /* driver program to test the above functions */
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(10);
        tree.root.left = new Node(8);
        tree.root.right = new Node(2);
        tree.root.left.left = new Node(3);
        tree.root.left.right = new Node(5);
        tree.root.right.right = new Node(2);
        if (tree.isSumProperty(tree.root) != 0)
            System.out.println("The given tree satisfies children" +
                " sum property");
        else
            System.out.println("The given tree does not satisfy children" +
                " sum property");
    }
}