DSA Programs

Data Structures and Algorithms

Fibonacci

Aim: To study and implement the Fibonacci sequence using recursive and iterative methods.

C++

#include <iostream>
using namespace std;

int fibonacci(int n)
{
    if(n <= 1)
        return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main()
{
    int n;

    cout << "Enter number: ";
    cin >> n;

    cout << "Fibonacci = " << fibonacci(n);

    return 0;
}

C++

#include <iostream>
using namespace std;

int main()
{
    int n;

    cout << "Enter number: ";
    cin >> n;

    int a = 0;
    int b = 1;

    if(n == 0)
    {
        cout << a;
    }
    else if(n == 1)
    {
        cout << b;
    }
    else
    {
        for(int i = 2; i <= n; i++)
        {
            int c = a + b;

            a = b;
            b = c;
        }

        cout << b;
    }

    return 0;
}

Algorithm: Fibonacci

Start.
Input the value of n.
If n is 0 or 1, return n.
For the recursive method, calculate Fibonacci(n-1) + Fibonacci(n-2).
For the iterative method, initialize the first two values as 0 and 1.
Repeatedly calculate the next value by adding the previous two values.
Display the Fibonacci value.
Stop.

Binary Search Tree

Aim: To study the Binary Search Tree (BST) structure and implement search operation using the BST property.

C++

#include <iostream>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int x)
    {
        val = x;
        left = NULL;
        right = NULL;
    }
};

TreeNode* searchBST(TreeNode* root, int val)
{
    if(root == NULL)
    {
        return NULL;
    }

    if(root->val == val)
    {
        return root;
    }
    else if(val < root->val)
    {
        return searchBST(root->left, val);
    }
    else
    {
        return searchBST(root->right, val);
    }
}

int main()
{
    TreeNode *root = new TreeNode(4);

    root->left = new TreeNode(2);
    root->right = new TreeNode(7);

    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);

    int val;

    cout << "Enter value to search: ";
    cin >> val;

    TreeNode *result = searchBST(root, val);

    if(result != NULL)
    {
        cout << "Node found: " << result->val << endl;
    }
    else
    {
        cout << "NULL" << endl;
    }

    return 0;
}

Algorithm: Search in Binary Search Tree

Start.
Set the root node as the current node.
If the current node is NULL, the value is not found.
If the value is equal to the current node value, the node is found.
If the value is smaller than the current node value, move to the left child.
Otherwise, move to the right child.
Repeat the process until the value is found or the current node becomes NULL.
Stop.

AVL / Balanced BST

Aim 1: To convert an unbalanced Binary Search Tree (BST) into a height-balanced Binary Search Tree while preserving all node values.

Aim 2: To balance a Binary Search Tree using inorder traversal and reconstruction.

C++

class Solution
{
public:

    vector<int> arr;

    void inorder(TreeNode* root)
    {
        if(root == NULL)
            return;

        inorder(root->left);

        arr.push_back(root->val);

        inorder(root->right);
    }

    TreeNode* build(int low, int high)
    {
        if(low > high)
            return NULL;

        int mid = (low + high) / 2;

        TreeNode* root = new TreeNode(arr[mid]);

        root->left = build(low, mid - 1);

        root->right = build(mid + 1, high);

        return root;
    }

    TreeNode* balanceBST(TreeNode* root)
    {
        inorder(root);

        return build(0, arr.size() - 1);
    }
};

Algorithm: Convert Unbalanced BST to Height-Balanced BST

Start.
Perform inorder traversal of the given BST.
Store all node values in an array.
The inorder traversal produces the values in sorted order.
Find the middle element of the array.
Create a new node using the middle element as the root.
Recursively build the left subtree using the left half of the array.
Recursively build the right subtree using the right half of the array.
Return the newly balanced BST.
Stop.

HackerRank Solutions

HackerRank versions of the DSA solutions.

HackerRank C++

Open HackerRank ↗

int fibonacci(int n)
{
    if(n <= 1)
        return n;

    return fibonacci(n - 1) + fibonacci(n - 2);
}

HackerRank C++

Open HackerRank ↗

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

    inOrder(root->left);

    cout << root->data << " ";

    inOrder(root->right);
}

HackerRank C++

Open HackerRank ↗

node * insert(node * root, int val)
{
    if(root == NULL)
    {
        node* temp = new node;

        temp->val = val;
        temp->left = NULL;
        temp->right = NULL;
        temp->ht = 0;

        return temp;
    }

    if(val < root->val)
    {
        root->left = insert(root->left, val);
    }
    else if(val > root->val)
    {
        root->right = insert(root->right, val);
    }

    root->ht = ht_hidden(root);

    int balance = BF_hidden(root);

    if(balance > 1 && val < root->left->val)
    {
        return LL_hidden(root);
    }

    if(balance < -1 && val > root->right->val)
    {
        return RR_hidden(root);
    }

    if(balance > 1 && val > root->left->val)
    {
        return LR_hidden(root);
    }

    if(balance < -1 && val < root->right->val)
    {
        return RL_hidden(root);
    }

    return root;
}