Convert a Binary Tree To hold Children Sum Property
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.
For example, the below tree doesn’t hold the children sum property, convert it to a tree that holds the property.
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
convert the tree in bottom up fashion by visiting leaf node then parent upward..
ReplyDeleteAt each step if sum of child nodes is greater or equal to parent node's value then only parent node is updated else we will have to update the child's value also...
how do you traverse a tree in bottom up fashion?
ReplyDeleteWould this work?
ReplyDeleteprivate BinaryTreeNode doCreateSumTree(BinaryTreeNode root) {
if (root!=null) {
doCreateSumTree(root.getLeftNode());
doCreateSumTree(root.getRightNode());
if (root!=null && root.getLeftNode()!=null && root.getRightNode()!=null) {
root.setData(root.getLeftNode().getData() + root.getRightNode().getData());
}
}
return root;
}