## Other: Check if a given Binary Tree is SumTree, Stack implementation

Check for SumTree

bool isLeaf (Node* root) {
    if (root->left == NULL && root->right == NULL) {
        return true;
    }
    else return false;
}


bool isSumTree (Node* root) {
    if (root == NULL || isLeaf(root)) {
        return true;
    }
    
    if (isSumTree(root->left) && isSumTree(root->right)) {
        int leftSum = 0, rightSum = 0;
        
        if (isLeaf(root->left)) {
            leftSum = left->val;
        }else if (root->left == NULL) {
            leftSum = 0;
        }else {
            leftSum = root->left->val * 2;
        }
        
        if (isLeaf(root->right)) {
            rightSum = right->val;
        }else if (root->right == NULL) {
            rightSum = 0;
        }else {
            rightSum = root->right->val * 2;
        }
        
        return root->val == (rightSum + leftSum);
    }
    
    return false;
}

The algorithm would be the same if we want to turn a tree to a valid sum tree ------------------------------------------------ Q: Implement a Stack class with O(1) min function. A: use an extra stack to contain all min values, O(n) space, use (push 2 * value - min to stack) to optimize space to O(1)