Skip to main content

Check Children Sum Property in a Binary Tree

The "Children Sum Property" is a property of binary trees, which states that the value of a node in a binary tree must be equal to the sum of the values of its two children.

The "Check Children Sum Property" refers to the process of checking whether a given binary tree satisfies this property. To check this property, you need to traverse the binary tree in a recursive manner, starting from the root node. For each node, you need to check whether the sum of the values of its two children is equal to the value of the node itself. If this property holds true for all the nodes in the tree, then the tree is said to satisfy the "Children Sum Property".

Check Children Sum Property in a Binary Tree

In other words, the "Check Children Sum Property" is a way to ensure that the values of nodes in a binary tree are consistent with the sum of the values of their children, which is an important property in many applications of binary trees, such as in constructing binary search trees and performing various tree-based algorithms.

Program List

/*
  C Program 
+ Check Children Sum Property in a Binary Tree
*/
#include<stdio.h>

#include<stdlib.h>
 //structure of Binary Tree node
struct Node {
  int data;
  struct Node *left, *right;
};
//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes

struct Node *insert(int data) {
  //create dynamic memory to new binary tree node
  struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
  if (new_node != NULL) {
    //set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL; //Initially node right-pointer is NULL
  } else {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  //return reference
  return new_node;

}

int children_sum(struct Node *root) {

  if (root == NULL || (root->left == NULL && root->right == NULL)) return 1;

  int leftData = 0, rightData = 0;

  if (root->left != NULL) {
    //get data of left child
    leftData = root->left->data;
  }
  if (root->right != NULL) {
    //get data of right child
    rightData = root->right->data;
  }

  if (root->data != leftData + rightData) {
    //when parent node data is not equal to child sum
    return 0;
  } else {
    //recursively call
    if (children_sum(root->left) && children_sum(root->right)) {
      return 1;
    }
    return 0;
  }

}


int main() {

  struct Node *root = NULL;
  /* Make A Binary Tree
  -----------------------
           7
         /   \
        4     3
       / \   /  \
      3   1 1    2
         / 
        1 
  */
  //Insertion of binary tree nodes
  root = insert(7);
  root->left = insert(4);
  root->right = insert(3);
  root->right->right = insert(2);
  root->right->left = insert(1);
  root->left->left = insert(3);
  root->left->right = insert(1);
  root->left->right->left = insert(1);


  if (children_sum(root)) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }
  //case 2
  root->left->right->data = 2;

  if (children_sum(root)) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  return 0;
}

Output

Yes
No

/*
C++ Program 
Check Children Sum Property in a Binary Tree
*/
#include<iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left, *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinaryTree {
  public:
  Node *root;
  BinaryTree() {
    this->root = NULL;
  }
  bool children_sum(Node *head) {
    if (head == NULL || (head->left == NULL && head->right == NULL)) {
      return true;
    }
    int leftData = 0, rightData = 0;
    if (head->left != NULL) {
      leftData = head->left->data;
    }
    if (head->right != NULL) {
      rightData = head->right->data;
    }
    if (head->data != leftData + rightData) {
      return false;
    } else {
      if (this->children_sum(head->left) && this->children_sum(head->right)) {
        return true;
      }
      return false;
    }
  }
};
int main() {
  BinaryTree obj;
  /* Make A Binary Tree
  -----------------------
           7
         /   \
        4     3
       / \   /  \
      3   1 1    2
         / 
        1 
  */
  obj.root = new Node(7);
  obj.root->left = new Node(4);
  obj.root->right = new Node(3);
  obj.root->right->right = new Node(2);
  obj.root->right->left = new Node(1);
  obj.root->left->left = new Node(3);
  obj.root->left->right = new Node(1);
  obj.root->left->right->left = new Node(1);
  if (obj.children_sum(obj.root)) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
  obj.root->left->right->data = 2;
  if (obj.children_sum(obj.root)) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}

Output

Yes
No

/*
Java Program 
Check Children Sum Property in a Binary Tree
*/

//Class of Binary Tree node
class Node {

  public int data;
  public Node left, right;
  //make a tree node
  public Node(int value) {
    //Assign field values
    data = value;
    left = null;
    right = null;
  }
}

public class BinaryTree {

  public Node root;

  public BinaryTree() {
    //set initial tree root to null
    root = null;

  }
  public boolean children_sum(Node head) {

    if (head == null || (head.left == null && head.right == null)) {
      return true;
    }

    int leftData = 0, rightData = 0;

    if (head.left != null) {
      //get data of left child
      leftData = head.left.data;
    }
    if (head.right != null) {
      //get data of right child
      rightData = head.right.data;
    }

    if (head.data != leftData + rightData) {
      //When parent node data is not equal to child sum
      return false;
    } else {
      //recursively call
      if (children_sum(head.left) && children_sum(head.right)) {
        return true;
      }
      return false;
    }

  }

  public static void main(String[] args) {
    //Make object of Binary Tree
    BinaryTree obj = new BinaryTree();


    /*Make A Binary Tree
      -----------------------
           7
         /   \
        4     3
       / \   /  \
      3   1 1    2
         / 
        1 
    */
    //Binary tree nodes
    obj.root = new Node(7);
    obj.root.left = new Node(4);
    obj.root.right = new Node(3);
    obj.root.right.right = new Node(2);
    obj.root.right.left = new Node(1);
    obj.root.left.left = new Node(3);
    obj.root.left.right = new Node(1);
    obj.root.left.right.left = new Node(1);


    if (obj.children_sum(obj.root)) {
      System.out.print("Yes\n");
    } else {
      System.out.print("No\n");
    }
    //case 2
    obj.root.left.right.data = 2;

    if (obj.children_sum(obj.root)) {
      System.out.print("Yes\n");
    } else {
      System.out.print("No\n");
    }

  }
}

Output

Yes
No

/*
C# Program 
Check Children Sum Property in a Binary Tree
*/
using System;
//Class of Binary Tree node
public class Node {

	public int data;
	public Node left, right;
	//make a tree node
	public Node(int value) {
		//Assign field values
		data = value;
		left = null;
		right = null;
	}
}

public class BinaryTree {

	public Node root;

	public BinaryTree() {
		//set initial tree root to null
		root = null;

	}
	public Boolean children_sum(Node head) {

		if (head == null || (head.left == null && head.right == null)) {
			return true;
		}

		int leftData = 0, rightData = 0;

		if (head.left != null) {
			//get data of left child
			leftData = head.left.data;
		}
		if (head.right != null) {
			//get data of right child
			rightData = head.right.data;
		}

		if (head.data != leftData + rightData) {
			//When parent node data is not equal to child sum
			return false;
		} else {
			//recursively call
			if (children_sum(head.left) && children_sum(head.right)) {
				return true;
			}
			return false;
		}

	}

	public static void Main(String[] args) {
		//Make object of Binary Tree
		BinaryTree obj = new BinaryTree();


		/*Make A Binary Tree
      -----------------------
           7
         /   \
        4     3
       / \   /  \
      3   1 1    2
         / 
        1 
    */
		//Binary tree nodes
		obj.root = new Node(7);
		obj.root.left = new Node(4);
		obj.root.right = new Node(3);
		obj.root.right.right = new Node(2);
		obj.root.right.left = new Node(1);
		obj.root.left.left = new Node(3);
		obj.root.left.right = new Node(1);
		obj.root.left.right.left = new Node(1);


		if (obj.children_sum(obj.root)) {
			Console.Write("Yes\n");
		} else {
			Console.Write("No\n");
		}
		//case 2
		obj.root.left.right.data = 2;

		if (obj.children_sum(obj.root)) {
			Console.Write("Yes\n");
		} else {
			Console.Write("No\n");
		}

	}
}

Output

Yes
No

# Python Program 
# Check Children Sum Property in a Binary Tree

class Node :
  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinaryTree :

  def __init__(self) :
    self.root = None
  
  def children_sum(self, head) :
    if (head == None or(head.left == None and head.right == None)) :
      return True
    
    leftData = 0
    rightData = 0
    if (head.left != None) :
      leftData = head.left.data
    
    if (head.right != None) :
      rightData = head.right.data
    
    if (head.data != leftData + rightData) :
      return False
    else :
      if (self.children_sum(head.left) and self.children_sum(head.right)) :
        return True
      
      return False
    
  
def main() :
  obj = BinaryTree()
  # Make A Binary Tree
  #           7
  #         /   \
  #        4     3
  #       / \   /  \
  #      3   1 1    2
  #         /
  #        1
  #  
  obj.root = Node(7)
  obj.root.left = Node(4)
  obj.root.right = Node(3)
  obj.root.right.right = Node(2)
  obj.root.right.left = Node(1)
  obj.root.left.left = Node(3)
  obj.root.left.right = Node(1)
  obj.root.left.right.left = Node(1)
  if (obj.children_sum(obj.root)) :
    print("Yes")
  else :
    print("No")
  
  obj.root.left.right.data = 2
  if (obj.children_sum(obj.root)) :
    print("Yes")
  else :
    print("No")
    
  

if __name__ == "__main__":
  main()

Output

Yes
No

# Ruby Program
# Check Children Sum Property in a Binary Tree
class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinaryTree 
	attr_reader :root
	attr_accessor :root
	def initialize() 
		@root = nil
	end
	def children_sum(head) 
		if (head == nil or(head.left == nil and head.right == nil)) 
			return true
		end
		leftData = 0
		rightData = 0
		if (head.left != nil) 
			leftData = head.left.data
		end
		if (head.right != nil) 
			rightData = head.right.data
		end
		if (head.data != leftData + rightData) 
			return false
		else 
			if (self.children_sum(head.left) and self.children_sum(head.right)) 
				return true
			end
			return false
		end
	end
end


def main() 
	obj = BinaryTree.new()
	# Make A Binary Tree
	#           7
	#         /   \
	#        4     3
	#       / \   /  \
	#      3   1 1    2
	#         /
	#        1
	#  
	obj.root = Node.new(7)
	obj.root.left = Node.new(4)
	obj.root.right = Node.new(3)
	obj.root.right.right = Node.new(2)
	obj.root.right.left = Node.new(1)
	obj.root.left.left = Node.new(3)
	obj.root.left.right = Node.new(1)
	obj.root.left.right.left = Node.new(1)
	if (obj.children_sum(obj.root)) 
		print("Yes\n")
	else 
		print("No\n")
	end
	obj.root.left.right.data = 2
	if (obj.children_sum(obj.root)) 
		print("Yes\n")
	else 
		print("No\n")
	end
end
main()

Output

Yes
No

/*
  Node JS Program
  Check Children Sum Property in a Binary Tree
*/
class Node {
	
	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree {

	constructor() {
		this.root = null;
	}
	children_sum(head) {
		if (head == null || (head.left == null && head.right == null)) {
			return true;
		}
		var leftData = 0;
		var rightData = 0;
		if (head.left != null) {
			leftData = head.left.data;
		}
		if (head.right != null) {
			rightData = head.right.data;
		}
		if (head.data != leftData + rightData) {
			return false;
		} else {
			if (this.children_sum(head.left) && this.children_sum(head.right)) {
				return true;
			}
			return false;
		}
	}
}
function main() {
	var obj = new BinaryTree();
	/* Make A Binary Tree
	  -----------------------
	           7
	         /   \
	        4     3
	       / \   /  \
	      3   1 1    2
	         / 
	        1 
	*/
	obj.root = new Node(7);
	obj.root.left = new Node(4);
	obj.root.right = new Node(3);
	obj.root.right.right = new Node(2);
	obj.root.right.left = new Node(1);
	obj.root.left.left = new Node(3);
	obj.root.left.right = new Node(1);
	obj.root.left.right.left = new Node(1);
	if (obj.children_sum(obj.root)) {
		process.stdout.write("Yes\n");
	} else {
		process.stdout.write("No\n");
	}
	obj.root.left.right.data = 2;
	if (obj.children_sum(obj.root)) {
		process.stdout.write("Yes\n");
	} else {
		process.stdout.write("No\n");
	}
}
main();

Output

Yes
No

<?php
/*
  Php Program
  Check Children Sum Property in a Binary Tree
*/
class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinaryTree {
  public $root;

  function __construct() {
    $this->root = null;
  }
  public  function children_sum($head) {
    if ($head == null || ($head->left == null && $head->right == null)) {
      return true;
    }
    $leftData = 0;
    $rightData = 0;
    if ($head->left != null) {
      $leftData = $head->left->data;
    }
    if ($head->right != null) {
      $rightData = $head->right->data;
    }
    if ($head->data != $leftData + $rightData) {
      return false;
    } else {
      if ($this->children_sum($head->left) && $this->children_sum($head->right)) {
        return true;
      }
      return false;
    }
  }
}

function main() {
  $obj = new BinaryTree();
  /* Make A Binary Tree
    -----------------------
             7
           /   \
          4     3
         / \   /  \
        3   1 1    2
           / 
          1 
  */
  $obj->root = new Node(7);
  $obj->root->left = new Node(4);
  $obj->root->right = new Node(3);
  $obj->root->right->right = new Node(2);
  $obj->root->right->left = new Node(1);
  $obj->root->left->left = new Node(3);
  $obj->root->left->right = new Node(1);
  $obj->root->left->right->left = new Node(1);
  if ($obj->children_sum($obj->root)) {
    echo("Yes\n");
  } else {
    echo("No\n");
  }
  $obj->root->left->right->data = 2;
  if ($obj->children_sum($obj->root)) {
    echo("Yes\n");
  } else {
    echo("No\n");
  }
}
main();

Output

Yes
No

/*
  Swift 4 Program
  Check Children Sum Property in a Binary Tree
*/
class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinaryTree {
  var root: Node? ;
  init() {
    self.root = nil;
  }
  func children_sum(_ head: Node? ) -> Bool {
    if (head == nil || (head!.left == nil && head!.right == nil)) {
      return true;
    }
    var leftData: Int = 0;
    var rightData = 0;
    if (head!.left != nil) {
      leftData = head!.left!.data;
    }
    if (head!.right != nil) {
      rightData = head!.right!.data;
    }
    if (head!.data != leftData + rightData) {
      return false;
    } else {
      if (self.children_sum(head!.left) && self.children_sum(head!.right)) {
        return true;
      }
      return false;
    }
  }
}
func main() {
  let obj: BinaryTree = BinaryTree();
  /* Make A Binary Tree
    -----------------------
             7
           /   \
          4     3
         / \   /  \
        3   1 1    2
           / 
          1 
  */
  obj.root = Node(7);
  obj.root!.left = Node(4);
  obj.root!.right = Node(3);
  obj.root!.right!.right = Node(2);
  obj.root!.right!.left = Node(1);
  obj.root!.left!.left = Node(3);
  obj.root!.left!.right = Node(1);
  obj.root!.left!.right!.left = Node(1);
  if (obj.children_sum(obj.root)) {
    print("Yes");
  } else {
    print("No");
  }
  obj.root!.left!.right!.data = 2;
  if (obj.children_sum(obj.root)) {
    print("Yes");
  } else {
    print("No");
  }
}
main();

Output

Yes
No
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment