Find the Lowest common ancestor in a binary tree

Problem Statement:

Find the Lowest common ancestor in a binary tree. Given the two nodes of a binary tree find the lowest common ancestor in the binary tree?

NOTE : THIS APPROACH IS FOR BINARY TREE ( NOT FOR BST)

Approach:

Lowest Common ancestor is the node to which the two nodes lie on the different sides,one node to its right and other node to its left.

If both the nodes are to its left than LCA is on left side of the node and if both the nodes are to its right than LCA is on right side of the node.

This can be implemented recursively using the bottom up approach with O(n) Complexity..

ASSUMPTION : Two nodes exist in the tree. Not Checking for there presence in this solution...

Here is the working C# Code. Just Copy and paste...

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LowestCommonAncestor
{
    // Tree Node Definition
    public class Tree
    {
        public int item;
        public Tree left;
        public Tree right;
        public Tree(int val)
        {
            item = val;
            left = null;
            right = null;
        }
    }

     class Program
    {
        static void Main(string[] args)
        {
            /* Constructed binary tree is
         10
       /   \
     7      30
   /  \    /
 4     8  16
/
2
*/
            Tree root = new Tree(10);
            root.left = new Tree(7);
            root.right = new Tree(30);
            root.left.left = new Tree(4);
            root.left.right = new Tree(8);
            root.right.left = new Tree(16);
            root.left.left.left = new Tree(2);

            Tree p = root.left.left.left;
            Tree q = root.left.right;

            Tree LCA = findLowestCommonAncestor(root, p, q);
            Console.WriteLine(LCA.item);
        }


        // Function To find the Lowest Common Ancestor
        public static Tree findLowestCommonAncestor(Tree root, Tree p, Tree q)
        {
            if (root == null)
                return null;

            if (root == p || root == q)
                return root;

            Tree left = findLowestCommonAncestor(root.left, p, q);
            Tree right = findLowestCommonAncestor(root.right, p, q);

            if (left != null && right != null)
                return root;

            if (left != null)
                return left;
            else
                return right;
        }
    }
}


Complexity :

Time Complexity : O(n), Since this is bottom up approach and each node is touched only once...


Hope you liked it.. For any suggestion or question please comment below...

Difference between sum of nodes at even level and sum of nodes at odd level in a Binary Tree

Problem Statement :

Given a binary tree, write a code that returns the difference between sum of nodes at even level and sum of nodes at odd level. Root is considered at level 0.

Solution :
This can be solved recursively. The bottom up approach is followed. Subtract the root with difference of its right and left nodes...


Here is the C# Code running Code. Just Copy and paste on VS..


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace diffOddAndEvenLevel
{
    // Tree Node Definition
    public class Tree
    {
        public int item;
        public Tree left;
        public Tree right;
        public Tree(int val)
        {
            item = val;
            left = null;
            right = null;
        }
    }

    // Program 
    class Program
    {
        static void Main(string[] args)
        {
            /* Constructed binary tree is
         10
       /   \
     7      30
   /  \    /
 4     8  16
/
2
*/
            Tree root = new Tree(10);
            root.left = new Tree(7);
            root.right = new Tree(30);
            root.left.left = new Tree(4);
            root.left.right = new Tree(8);
            root.right.left = new Tree(16);
            root.left.left.left = new Tree(2);
            Console.WriteLine(diffLevels(root));
        }
      
       // Function calculating the difference
        public static int diffLevels(Tree root)
        {
            if (root == null)
            {
                return 0;
            }
           // Subtracting the value from root and difference from its right and left..
            return root.item - diffLevels(root.left) - diffLevels(root.right);
        }

    }
}

Complexity :
Time Complexity :  O(n) , Since every node is visited only once and solution is bottom up approach..


Hope you liked it.. Please leave the comments below...

Generate 1 to N random number with no duplication.

Problem Statement :

Generate 1 to N  random number with no duplication.

Approach
This can be solved easily with Knuth Fisher Yates Algorithm.

STEP 1: Initialize an array of size and fill the values 1 to n in it..
STEP 2: Generate a random number between 1 - i and swap it with i + 1. Do it in decreasing loop of i .


Here is the C# Code for Knuth Fisher Yates Algorithm..


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RandomGenerator
{
    class Program
    {
        static void Main(string[] args)
        {
            generateRandom(10);
        }

        public static void generateRandom(int N)
        {
            if (N < 1)
                return;

            // Intializing the array of size N and fill the sequential values
            int[] arr = new int[N];
            for (int i = 0; i < N; i++)
            {
                arr[i] = i + 1;
            }

            // Randomizing the values by swapping the values from random value between i and Zero
            // This is Knuth Algorithm
            Random rd = new Random();
            for (int i = N - 1; i >= 0; i--)
            {
                int num = rd.Next(i);
                // Swapping array index
                swap(arr, num, i);
            }

            // Printing the Randomized array...
            for (int i = 0; i < N; i++)
            {
                Console.Write(arr[i] + ", ");
            }
        }

        public static void swap(int[] arr, int x, int y)
        {
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
    }
}

Complexity :

Time Complexity : O(n)

Space Complexity : O(n)

Please leave any question or suggestion in the comments section below...

Kth largest in a BST

Problem Statement 

A Binary Search Tree is given and we need to find the Kth largest in that tree. Root is given...

Approach :

Two approaches can be taken.
1. Recursive approach
2. Iterative Approach

Both the approaches code is below in C#


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace kthElement
{
// Tree Node Definition
    public class Tree
    {
        public int item;
        public Tree left;
        public Tree right;
        public Tree(int val)
        {
            item = val;
            left = null;
            right = null;
        }
    }

// Program 
    class Program
    {
        static void Main(string[] args)
        {
            /* Constructed binary tree is
         10
       /   \
     7      30
   /  \    /
 4     8  16
/
2
*/
            Tree root = new Tree(10);
            root.left = new Tree(7);
            root.right = new Tree(30);
            root.left.left = new Tree(4);
            root.left.right = new Tree(8);
            root.right.left = new Tree(16);
            root.left.left.left = new Tree(2);
            for (int i = 1; i < 5; i++)
            {
                int k = i;
                findKthElementRecursive(root, ref k);

                k = i;
                Tree kthElement = findKthElementIterative(root, k);
                if (kthElement != null)
                {
                    Console.WriteLine(kthElement.item);
                }
            }
        }

         // Function Implementing Recursive approach

         public static void findKthElementRecursive(Tree root, ref int k)
        {         
           if (root == null)
                return;

            findKthElementRecursive(root.left,ref k);
            k--;
            if (k == 0)
            {
                Console.WriteLine(root.item);
            }
            findKthElementRecursive(root.right, ref k);
        }

      // Function Implementing iterative approach
     //  1. Push current focus tree to stack
      //  2. Update the current focus to left sub-tree
      //  3. Pop out tree when current focus is null
      //  4. Decrement K by 1 and if K is Zero Return the current
     //   5. Else Set focus to the pop-up node's right
        public static Tree findKthElementIterative(Tree root, int k)
        {
            if (root == null)
                return null;
            Tree current = root;
            Stack<Tree> st = new Stack<Tree>();
            while (st.Count > 0 || current != null)
            {
                if (current != null)
                {
                    st.Push(current);
                    current = current.left;
                }
                else
                {
                    current = st.Pop();
                    k--;
                    if (k == 0)
                        return current;
                    current = current.right;
                }
            }
            return null;
        }
    }
}

Time Complexity :
Recursive approach :  O(n)
Iterative approach   :  O(n)

Hope you must have liked it...

Merge the two sorted arrays into one of the array of larger size

Problem Statement :

Given two sorted arrays, one of size N and second of size M+N.. Merge them into the larger array which contains N empty spaces at the end..

Example :

 Array 1 = {3,7,11,14,15,0,0,0,0} (Size : 5 + 4)
 Array 2 = {1,2,11,16} (Size : 4)

Result :
 Merged to  Array1 = {1,2,3,7,11,11,14,15,16}

Approach :


1.Start the loop from end to beginning
2. Track the tail indexes of the two arrays
3. After Merging the position is equal to arr1Tail+arr2Tail+1 (until both index reaches 0)
4. If the arr2Tail is larger than or equal to 0 after merging, adding the remaining values to the merged array

C# Code 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace MergeTwoSortedArray

{

    class Program

    {

        static void Main(string[] args)

        {

            int[] arr1 = new int[] { 1, 2, 2, 3, 4, 5,0,0,0,0,0};

            int[] arr2 = new int[] { 2, 2, 7 };

            merge(arr1, arr2, 5);

            for (int i = 0; i < arr1.Length; i++)

            {

                Console.Write(arr1[i] + ",");

            }

        }

       // Function Implementing Merge

     // arr1 is larger array and arr2 is smaller array

    // Usedindex is the index of the arr1 last valid value in arr1

        public static void merge(int[] arr1, int[] arr2, int usedIndex)

        {

            int longused = usedIndex;

            int shortarr = arr2.Length - 1;

            while (shortarr >= 0 && longused >= 0)

            {

                if (arr2[shortarr] > arr1[longused])

                {

                    arr1[shortarr + longused + 1] = arr2[shortarr];

                    shortarr--;

                }

                else

                {

                    arr1[shortarr + longused + 1] = arr1[longused];

                    longused--;

                }

            }

           while(shortarr >= 0)

            {

                arr1[shortarr] = arr2[shortarr];

                shortarr--;

            }                     

        }

    }

}

Complexity :

Computational Complexity : O(M+ N) 

Space Complexity : Constant 

Longest Common Sub sequence

What is Longest Common Sub sequence?


Longest Common Sub sequence is longest consecutive/non consecutive matching characters of the two strings..

Lets take two strings

Str1 = "XMJYAUZ"
Str2 = "MZJAWXU"

Longest common subsequence is "MJAU"..

This problem can be very easily solved using dynamic programming.

Here is the C# Code below

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Math;

namespace maxCommonSubstring

{

    class Program

    {

        static void Main(string[] args)

        {

            string str1 = "hello12india2125";

            string str2 = "hel2125ino";

             Console.WriteLine(LongestCommonSubsequence(str1, str2));

        }

        public static int LongestCommonSubsequence(string str1, string str2)

        {

            int maxSubSeq = 0;

           // Create 2-d Array

            int[,] arr = new int[str1.Length + 1, str2.Length + 1];

          // Initialize 2 - d array 

        // Note only zeroth column and zeroth row is assigned value 0

      // Can be skipped as well as by default they are Zero in C#

            for (int i = 0; i < str2.Length; i++)

            {

                arr[0, i] = 0;

            }

            for (int i = 0; i < str1.Length; i++)

            {

                arr[i, 0] = 0;

            }

         // Start Filling the table 

        // if Character match add 1 to diagonal element of 2 - d array and fill it

       // Else put the max of the elements on its top or  on its left ..

      // Keep track of the size using a variable "maxSubSeq"

            for (int i = 1; i <= str1.Length; i++)

            {

                for (int j = 1; j <= str2.Length; j++)

                {

                     if (str1[i - 1] == str2[j - 1])

                    {

                        //Character match add 1 to diagonal element of 2 - d array

                        arr[i, j] = arr[i - 1, j - 1] + 1;

                        if (arr[i, j] > maxSubSeq)

                        {

                            maxSubSeq = arr[i, j];

                        }

                    }

                    else

                    {

                          // Else put the max of the elements on its top or  on its left ..

                          arr[i, j] = Math.Max(arr[i, j - 1] ,  arr[i - 1, j]);

                    }

                }

            }

            return maxSubSeq;

     }

}

Complexity :

Space complexity O(n*m) since we are using the 2-d array where n and m are length of the given 2 strings

Computational complexity O(n*m) since we filling the 2-d array in loops  where n and m are length of the given 2 strings

Hope you  liked it....