Day18: (Binary Tree)

Level order Traversal Solved on: Aug 1st 2020

int height (Node *node) {
    int lh, rh;
    if (node==NULL) {
        return 0;
    }
    
    lh=height(node->left);
    rh= height(node->right);
    
    if (lh>rh){
        return lh+1;
    } else {
        return rh+1;
    }
}

  
/* Print nodes at a given level */
void printGivenLevel(Node* root, int level, vector<int> &v) {  
    if (root == NULL)  
        return;  
    if (level == 1)  
        v.push_back(root->data);
    else if (level > 1)  
    {  
        printGivenLevel(root->left, level-1, v);  
        printGivenLevel(root->right, level-1, v);  
    }  
}  

vector<int> levelOrder(Node* node) {
    vector<int> v;
    if (node == NULL) {
        return v;
    }
    
    int h=height(node);
    int i;
    for (i=0;i<=h;i++) {
        printGivenLevel(node, i, v);
    }
    return v;
}

Height of a Binary Tree Solved on: Aug 1st 2020

int maxDepth(TreeNode* node) {
    int lh, rh;
    if (node==NULL) {
        return 0;
    }

    lh=maxDepth(node->left);
    rh= maxDepth(node->right);

    if (lh>rh){
        return lh+1;
    } else {
        return rh+1;
    }
}

Diameter of Binary Tree Solved on: Aug 1st 2020

int diameterOfBinaryTree(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    int lh=0, rh=0, ld=0, rd=0;
    
    lh = height(root->left);
    rh = height(root->right);
    
    int th = lh +  rh ;
    
    ld=diameterOfBinaryTree(root->left);
    rd=diameterOfBinaryTree(root->right);
    
    int diameter = max(ld, rd);
    return max(diameter, th);
    
}

int height(TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    else {
        return max(height(node->left)+1, height(node->right)+1);
    }
}

Check if Binary tree is height balanced or not Solved on: Aug 2nd 2020

int height(Node *root) {
    if (root==NULL) {
        return 0;
    }
    
    return 1 + max(height(root->left), height(root->right)); 
}

bool isBalanced(Node *root) {
    int lh, rh;
    if (root==NULL) {
        return 1;
    }
    
    lh=height(root->left);
    rh=height(root->right);
    
    if (abs(lh-rh) <=1 && isBalanced(root->left) && isBalanced(root->right)) {
        return true;
    }
    return false;
}

Lowest Common Ancestor of a Binary Tree Solved on: Aug 2nd 2020

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
    if ( !root || root->val == p->val || root->val == q->val ) {
        return root;
    }
    
    TreeNode* left_lca  = lowestCommonAncestor(root->left, p, q);
    TreeNode* right_lca  = lowestCommonAncestor(root->right, p, q);
    
    
    if (left_lca && right_lca) {
        return root;
    }
    
    return left_lca != NULL ? left_lca : right_lca;
    
}

Check if two trees are identical or not Solved on: Aug 2nd 2020

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p==NULL && q==NULL ) {
        return true;
    }
    if (p != NULL && q != NULL) {
        return p ->val == q->val &&  isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
    return false;
}