CareerCup

Assume we have access to the root and the tree is complete.

private boolean fixTree(Node node) {
	if (node == null) {
		return false;
	}
	if (node.left == null || node.right == null) {
		// The node is a leaf, no need to fix
		return node.value;
	}
	node.value = fixTree(node.left) && fixTree(node.right);
	return node.value;
}

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;
    }
}

@PenChief: I think that's the best solution, as well with stopping when value doesn't toggle anymore. I was surprised he accepted the parent pointer in the Node. How ever it's easy enough to fix that.

Tree * fixTree(Tree* root){
	if (root == NULL || (root->left == NULL && root->right == NULL))
		return root;
 	Tree *l_val=fixTree(root->left);
	Tree *r_val=fixTree(root->right);
	
	if(root->data != (l_val->data && r_val->data))
		root->data = !root->data;
	return root;
}

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.

This is similar to bubble-up operation in heaps.