Question: Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node (You cannot change structure of tree and cannot decrement value of any node).
For example, the below tree doesn’t hold the children sum property, convert it to a tree that holds the property.
50
/ \
/ \
7 2
/ \ /\
/ \ / \
3 5 1 30
Now convert the root, we have to increment left subtree for converting the root.
50
/ \
/ \
19 31
/ \ / \
/ \ / \
14 5 1 30
Java Implementation:
static void convertMaxSumTree(Node root){
if(root == null || (root.left == null && root.right == null)) return;
int sum = 0 ;
convertMaxSumTree(root.left);
convertMaxSumTree(root.right);
if(root.left != null){
sum += root.left.data;
}
if(root.right != null)
sum += root.right.data;
int diff = sum - root.data;
if(diff > 0){
root.data += diff;
}else if(diff < 0){
increaseValue(root, -diff);
}
}
private static void increaseValue(Node root, int diff) {
//if(root == null) return;
if(root.left != null)
{
root.left.data += diff;
increaseValue(root.left, diff);
}else if(root.right != null)
{
root.right.data += diff;
increaseValue(root.right, diff);
}
}
Here is code:
ReplyDeletestatic void connectNodes(Node root){
if(root == null) return;
if(root.left == null && root.right == null) return;
if(root.left != null)
{
if(root.right != null) root.left.next = root.right;
else{
if(root.next == null) root.left.next = root.next;
else{ Node tmp = root;
while(tmp != null && tmp.next.left == null && tmp.next.right == null){
tmp = tmp.next;
}
if(tmp == null) root.left.next = null;
else if(tmp.next.left != null) root.left.next = tmp.next.left;
else root.left.next = tmp.next.right;
}
}
}
if(root.right != null)
{
if(root.next == null) root.right.next = null;
else{
Node tmp = root.next;
while(tmp != null && tmp.left == null && tmp.right == null){
tmp = tmp.next;
}
if(tmp == null)
root.right.next = null;
else if(tmp.left != null) root.right.next = tmp.left;
else root.right.next = tmp.right;
}
}
connectNodes(root.left);
connectNodes(root.right);
}
Method :1
ReplyDeletestatic void connectNodeAtSameLevel(Node root){
if(root == null) return;
Queue q = new LinkedList();
q.add(root);
q.add(null);
while(true)
{
Node curr = q.poll();
if(curr != null)
{
curr.next = q.peek();
if(curr.left != null)
{
q.add(curr.left);
}
if(curr.right != null)
{
q.add(curr.right);
}
}else if(!q.isEmpty()){
q.add(null);
}
else{
break;
}
}
}