HackerRank‐Trees

---

title: Trees categories: - interview-preparation-kit - HackerRank comments: false

Tree: Height of a Binary Tree

int height(Node* root) {
        // Write your code here.
        if(!root) return 0;
        else if(!root->left && !root->right) return 0;
        else return 1+max(height(root->left), height(root->right));
    }

Binary Search Tree : Lowest Common Ancestor

Node *lca(Node *root, int v1,int v2) {
		// Write your code here.
        if(v1 > v2) swap(v1,v2);
        if(root->data < v1 && root->data < v2) return lca(root->right, v1, v2);
        else if(root->data > v1 && root->data > v2) return lca(root->left, v1, v2);
        else return root;
    }

Trees: Is This a Binary Search Tree?

 bool check(Node *root, int mn, int mx){
        if(!root) return true;
        bool left = check(root->left, mn, root->data);
        bool right = check(root->right, root->data, mx);
        if(root->data >= mx || root->data <=mn) return false;
        else return left && right;
        
    }
	bool checkBST(Node* root) {
        int mn = 0;
        int mx = 10000;
        return check(root, mn, mx);
	}

Tree: Huffman Decoding

void decode_huff(node * root, string s) {
    string ret ;
    int i =0;
    while(i<s.size()){
        node * p =root;
        while(p){
            if(i<s.size() && p->right &&s[i]=='1'){
                i++;
                p=p->right;
            }
            else if(i<s.size() && p->left && s[i]=='0'){
                i++;
                p=p->left;
            }   
            if(!p->left && !p->right){
                 ret+= p->data;
                 break;
            }
        }
    }
    cout<<ret<<endl;
}

Balanced Forest