//Question: WAP that sum up all one child parent nodes without globle variable
// 3
// / \
// 4 5
// / \ \
// 6 8 9
// /
// 7
//output 8+5=13
//Algorithms steps
/* steps 1 :check root is null return 0
* steps 2: check root has only one child if yes check its root->left->left or root->right- *>left is null if yes return root.data
* steps 3: repeat the process
*/
/*special case:
* input tree 9
* / \
* null 7
* / \
* 6 null
* output is 7
*
*/package josh;
public class OneChildParentSum {
public static void main(String[] args) {
Node node1 = new Node(6, null, null);
Node node2 = new Node(7, null, null);
Node node3 = new Node(9, null, null);
Node node4 = new Node(8, node2, null);
Node node5 = new Node(4, node1, node4);
Node node6 = new Node(5, null, node3);
Node node7 = new Node(3, node5, node6);
Node node8 = new Node(6, null, null);
Node node9 = new Node(7, node8, null);
Node node10 = new Node(9, null, node9);
System.out.println(parentSum(node7));
System.out.println(parentSum(node10));
}
static int parentSum(Node root)
{
if (root == null)
return 0;
else if ((root.left == null && root.right != null)|| (root.left != null && root.right == null))
{
if ((root.right.right == null && root.right.left == null)|| (root.left.left == null && root.left.right == null))
return root.data;
else return parentSum(root.left)+parentSum(root.right);
}
else {
return parentSum(root.left)+parentSum(root.right);
}
}
static class Node {
int data;
Node left;
Node right;
public Node(int data, Node left, Node right) {
super();
this.data = data;
this.left = left;
this.right = right;
}
// you can also use static factory method for creation of node
// refer http://mylovejava678.blogspot.in/
public static Node makeNode(int data, Node left, Node right) {
return new Node(data, left, right);
}
public static Node makeRNode(int data, Node right) {
return new Node(data, null, right);
}
public static Node makeLNode(int data, Node left) {
return new Node(data, left, null);
}
}
}