Facebook Interview Question
Country: Israel
Here is the solution I gave to the interviewer:
#include "CommonHeader.h"
struct TreeNode {
TreeNode* parent;
TreeNode* left;
TreeNode* right;
bool value;
TreeNode() : parent(NULL), left(NULL), right(NULL) {}
/**
* @brief return true if this node value was actually fixed. False otherwise
* @return
*/
bool updateValue() {
bool oldValue = this->value;
this->value = this->left && this->right; // same as LOGICAL AND
return oldValue != this->value;
}
};
void fixTree(TreeNode* node) {
node->value = !node->value;
TreeNode* cur = node->parent;
while(cur) {
if(!cur->updateValue())
break;
cur = cur->parent;
}
}
Please tell me if there is any bugs.
private void fixTree(TreeNode root, TreeNode node)
{
fixTreeUtil(root, node);
}
private boolean fixTreeUtil(TreeNode root, TreeNode node)
{
if(root == null) return false;
if(root == node) return true;
boolean cl = fixTreeUtil(root.left, node);
boolean cr = fixTreeUtil(root.right, node);
if(cl || cr)
{
root.val = root.left.val && root.right.val;
return true;
}
else return false;
}
class TreeNode {
boolean val;
TreeNode left;
TreeNode right;
}
@PenChief
Small correction here:
this->value = this->left && this->right;
This line will set value = 1 as long as we have valid left and right child. We actually need to read the value of left and right child in order to set the value of parent to Logical AND.
Please correct me if I'm wrong here.
Assume we have access to the root and the tree is complete.
- Jason Saruulo September 19, 2017