Kanchan Rai

Day 19: 100 Days of DSA

Advanced Binary Trees

Kanchan Rai's photo
Kanchan Rai
·

6 min read

Table of contents

Welcome to Day 19 of my 100 Days of DSA challenge! Today, I solved five problems focused on binary trees. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!

/In our previous blog, we explored the concept of binary trees and discussed various traversal techniques. Today, we’ll take a deeper dive into some exciting and challenging problems related to binary trees.

1. Solve the "check if a binary tree is balanced" problem.

To determine if a binary tree is balanced, you need to ensure the following:

  1. The difference in height between the left and right subtrees of every node in the tree is at most 1.

  2. Both the left and right subtrees themselves must also be balanced.

To solve this question we can take help of recursion.

Code:

// To check if a binary tree is balanced

#include<iostream>
using namespace std;

class Node{
    public:
      int data;
      Node* left;
      Node* right;

      Node(int data){
        this->data=data;
        this->left=NULL;
        this->right=NULL;
      }

};

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

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

        if(abs(lh-rh)<=1 && isBalanced(root->left) && isBalanced(root->right)){
            return true;
        }
    }
    return false;
}

int main(){
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->left = new Node(8);

    if (isBalanced(root))
        cout << "The tree is balanced";
    else
        cout << "The tree is not balanced";
    return 0;

}

Output:

2. Solve the "find the lowest common ancestor of two nodes in a binary tree" problem.

The "Find the Lowest Common Ancestor (LCA) of two nodes in a binary tree" problem requires finding the lowest node in the tree that is an ancestor of both the given nodes p and q.

The cases that were identified are:

  • If p or q is the root node, the root itself is the LCA.

  • If p and q are in different subtrees of a node, that node is the LCA.

  • If p and q are in the same subtree, continue searching in that subtree.

Code:

// Solve the "find the lowest common ancestor of two nodes in a binary tree" problem.

#include<iostream>
using namespace std;

class Node{
    public:
      int data;
      Node* left;
      Node* right;

      Node(int data){
        this->data=data;
        this->left=NULL;
        this->right=NULL;
      }

};

Node* LowestCommonAncestor(Node* root, int p , int q){
    //Empty tree
    if(root==NULL){
        return NULL;
    }

    if(root->data==p || root->data==q){
        return root;
    }

    Node* left=LowestCommonAncestor(root->left,p,q);
    Node* right=LowestCommonAncestor(root->right,p,q);

    // nodes are in different subtrees
    if(left!=NULL && right!=NULL){
        return root;
    }
    //return non null subtree
    return left != NULL ? left : right;
}

int main(){
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->left = new Node(8);

    cout<<"The lowest common ancestor of "<<2<<" and"<<3<<" is:"<<LowestCommonAncestor(root,2,3)->data;
}

Output:

3. Solve the "convert a binary tree to its mirror" problem.

The problem "Convert a binary tree to its mirror" involves transforming a given binary tree such that its left and right children at every level are swapped. This results in a "mirror image" of the original binary tree.

To convert a binary tree to its mirror, we need to:

  1. Traverse the tree.

  2. Swap the left and right child nodes of each node.

  3. Perform this operation recursively for all nodes in the tree.

Code:

// To convert a binary tree to its mirror
#include<iostream>
using namespace std;

class Node{
    public:
      int data;
      Node* left;
      Node* right;

      Node(int data){
        this->data=data;
        this->left=NULL;
        this->right=NULL;
      }

};

Node* mirrorTree(Node* root){
    if(root==NULL){
        return NULL;
    }

    Node*temp=root->left;
    root->left=root->right;
    root->right=temp;
    mirrorTree(root->left);
    mirrorTree(root->right);
}

void inorderTraversal(Node*root){
    if(root!=NULL){
    inorderTraversal(root->left);
    cout<<root->data<<"-";
    inorderTraversal(root->right);
    }

}

int main(){
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->left = new Node(8);
    cout<<"The Tree is:"<<endl;
    inorderTraversal(root);
    cout<<endl;
    cout<<"The mirror tree is:"<<endl;
    mirrorTree(root);
    inorderTraversal(root);
}

Output:

The output is in the form of inorder traversal of tree.

4. Solve the "zigzag level order traversal of a binary tree" problem.

The problem "Zigzag Level Order Traversal of a Binary Tree" involves traversing the tree level by level, but alternating the direction of traversal at each level.

To solve this we can:

  • Traverse the first level (root) from left to right.

  • Traverse the second level from right to left.

  • Traverse the third level from left to right, and so on.

Code:

#include <iostream>
#include <vector>
#include <queue>
#include<algorithm>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = NULL;
        right = NULL;
    }
};

vector<vector<int>> zigzagLevelOrder(Node* root) {
    vector<vector<int>> result;
    if (root == NULL) return result;

    queue<Node*> q;
    q.push(root);
    bool leftToRight = true;

    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> level;

        for (int i = 0; i < levelSize; i++) {
            Node* currentNode = q.front();
            q.pop();
            level.push_back(currentNode->data);

            if (currentNode->left) q.push(currentNode->left);
            if (currentNode->right) q.push(currentNode->right);
        }

        // Reverse the level if needed (for zigzag)
        if (!leftToRight) {
            reverse(level.begin(), level.end());
        }

        result.push_back(level);
        leftToRight = !leftToRight;  // Toggle the direction for next level
    }

    return result;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);

    vector<vector<int>> result = zigzagLevelOrder(root);

    // Output the result
    for (const auto& level : result) {
        for (int val : level) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

Output:

5. Solve the "flatten a binary tree to a linked list" problem.

To flatten a binary tree to a linked list, the goal is to convert the binary tree into a "linked list" where each node's right pointer points to the next node in a pre-order traversal, and the left pointer is set to NULL.

  • We can use recursive approach to achieve this flattening.

  • During the recursive call, traverse the tree and modify the pointers as needed.

Code:

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int val) {
        data = val;
        left = NULL;
        right = NULL;
    }
};

void flatten(Node* root) {
    if (root == NULL) return;

    // If left child exists, flatten it first
    if (root->left) {
        flatten(root->left);

        // Save the right subtree
        Node* temp = root->right;

        // Move the left subtree to the right
        root->right = root->left;
        root->left = NULL;

        // Find the rightmost node of the new right subtree
        Node* current = root->right;
        while (current->right) {
            current = current->right;
        }

        // Attach the saved right subtree
        current->right = temp;
    }

    // If no left child, move to the right
    flatten(root->right);
}

void printFlattenedTree(Node* root) {
    while (root) {
        cout << root->data << " ";
        root = root->right;
    }
    cout << endl;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(5);
    root->left->left = new Node(3);
    root->left->right = new Node(4);
    root->right->right = new Node(6);

    cout << "Original tree: " << endl;
    printFlattenedTree(root);

    flatten(root);

    cout << "Flattened tree: " << endl;
    printFlattenedTree(root);

    return 0;
}

Output:

What did the binary tree say to its parent? "I’m rooting for you!"
Hope you got good insights from this blog! Ciao~

BinaryTreesDSA
Â