Validating Binary Tree

Was browsing through Medium coding problems of Leetcode( Oh yeah. I think Im at this level ) when I stumble upon this one — validating binary tree. Pfft. You dummy, NO WAY this is medium. Turns out it is harder than I thought ^^, not because it is  hard but because of my stupid mistakes….

http://i.imgur.com/jn7drKc.gifv

To brush up on binary tree a little bit : a kind of tree where its left sub tree’s node value is less than the roots and right sub tree greater than. So we just in order traverse the root and check the aforementioned rule and we’re done ? and that is what the function signature gives us, just the root:

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
  bool isValidBST(TreeNode* root){
        if(root){
            if (root->left){
                if(root->left->val >= root->val)
                    return false;
            }
            if(root->right){
                if(root->right->val <= root->val)
                    return false;
            }
        }
        return true;
    }

 

This does not hold for cross branch property violation. What if there is a number on the right sub tree(from the root) that is valid on those branch but is less than the one on the left tree(from the root).

 

Invalid Binary tree
6 < 15 but not < 10

 

So how do we make sure the tree is valid during our iteration ? We can’t. But we could look at the result and conclude right away if it is valid binary tree. Remember the outcome of binary tree in order traversal (why i bolded it above) is a sorted array. Ah ha (Prove it ? by binary tree’s nature duh). Therefore, we just have an array holding the result and check if it is sorted and we’re done….Except it is hair scratching:


for(int i = 0; i < visiteds.size() - 1; i++){
    if(visiteds[i+1] <= visiteds[i])<b>;</b>
        return false;
}

If the vector is empty, it will return max_int – 1 which 0 is always less than, bruhhh, bugs!!!

Really?
MAX_INT(64bit) – 1 ?

Add check for empty in the for loop then. Still no go. What the hell. Took me an awful while to realize that there is a SEMICOLON at the end of the if statement, Woh. man . Fixed that and killed the challenge.

Anyway, Kudo Leetcode for the Tree visualizer:

Beat Hackerank a mile
The Leetcode tree node visualizer

This has taught me a lesson. Always be humble no matter how easy things seem to be. It is easy that kills you. “Know thy enemy”(Sun Tzu). Don’t quickly come to conclusion without thinking before hands.

King saids about his writing desk : “It’s not in the middle of the room. It’s the other way around” so you can focus. I had my desk to the corner away from my bed and I should fight the thought of retreating back to lying down…

Phew, enjoy a chinese music

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s