Sort 3 number using only if

We are trying to sort three numbers using If-Else only and no sorting algorithm.
There are couple of possibilities but the easiest one with minimum comparison is presented here.

C++ Code

       
#include <iostream>

using namespace std;

void smallSort(int &a, int &b, int &c) {
    if(a > b) { // if a is greater than b, swap them        
        int temp = a;
        a = b;
        b = temp;
    }

    if(a > c) { // if a is greater than c, swap them        
        int temp = a;
        a = c;
        c = temp;
    }

    // Now A is the smallest. We just need to compare B and C and swap if needed.    
    if(b > c) {
        int temp = b;
        b = c;
        c = temp;
    }
}

int main(){
    int a = 14;
    int b = -90;
    int c = 2;
    smallSort(a, b, c);
    cout << a << ", " << b << ", " << c << endl;

    return 0;
}



 

Heap sort

A Heap is an almost complete binary tree.In this tree, if the maximum level is i, then, upto the (i-1)th level should be complete. At level i, the number of nodes can be less than or equal to 2^i. If the number of nodes is less than 2^i, then the nodes in that level should be completely filled, only from left to right.

The property of an ascending heap is that, the root is the lowest and given any other node i, that node should be less than its left child and its right child. In a descending heap, the root should be the highest and given any other node i, that node should be greater than its left child and right child.

To sort the elements, one should create the heap first. Once the heap is created, the root has the highest value. Now we need to sort the elements in ascending order. The root can not be exchanged with the nth element so that the item in the nth position is sorted. Now, sort the remaining (n-1) elements. This can be achieved by reconstructing the heap for (n-1) elements.

Following is the java code which sorts an array in ascending order using Heap Sort:
(Time Complexity of the algorithm is - O(nlogn))

public class HeapSort {

    private static int getLeft(int i){
        return 2*i+1;
    }

    private static int getRight(int i){
        return 2*i+2;
    }

    private static void buildHeap(int[] arr){
        for(int i=(arr.length-2)/2; i>=0; i--){
           heapify(arr, arr.length, i);
        }
    }

    private static void heapify(int[] arr, int heapSize, int k){
        int leftChild = -1;
        if(k >= heapSize){
            return;
        }
        if(getLeft(k) < heapSize){
            leftChild = arr[getLeft(k)];
        }

        int rightChild = -1;
        if(getRight(k) < heapSize){
            rightChild = arr[getRight(k)];
        }

        if(arr[k] > leftChild && arr[k] > rightChild){
            return;
        }

        if(leftChild < rightChild){
            swap(arr, k, getRight(k));
            heapify(arr, heapSize, getRight(k));
        }else {
            swap(arr, k, getLeft(k));
            heapify(arr, heapSize, getLeft(k));
        }

    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int x[] = new int[]{9,3,1,10,15,16,8,7,4,5,89};
        buildHeap(x);
        int heapSize = x.length;
        for(int i = x.length-1; i>=0; i--){
            swap(x, 0, heapSize-1);
            --heapSize;
            heapify(x, heapSize, 0);
        }

        System.out.println(Arrays.toString(x));
    }
}

Reverse the bits in an integer

Coming Soon...

Count bits set in an integer

Coming Soon...

Threaded binary tree

Coming Soon...

New node to a Binary Search Tree

Coming Soon...

Implement Depth First Search (DFS)

Depth First Search (DFS) is a generalization of the preorder traversal. Starting at some arbitrarily chosen vertex v, we mark v so that we know we've visited it, process v, and then recursively traverse all unmarked vertices adjacent to v (v will be a different vertex with every new method call). When we visit a vertex in which all of its neighbors have been visited, we return to its calling vertex, and visit one of its unvisited neighbors, repeating the recursion in the same manner. We continue until we have visited all of the starting vertex's neighbors, which means that we're done. The recursion (stack) guides us through the graph. 

Implement Breadth First Search (BFS)

Breadth First Search (BFS) searches the graph one level (one edge away from the starting vertex) at a time. In this respect, it is very similar to the level order traversal that we discussed for trees. Starting at some arbitrarily chosen vertex v, we mark v so that we know we've visited it, process v, and then visit and process all of v's neighbors. Now that we've visited and processed all of v's neighbors, we need to visit and process all of v's neighbors neighbors. So we go to the first neighbor we visited and visit all of its neighbors, then the second neighbor we visited, and so on. We continue this process until we've visited all vertices in the graph. We don't use recursion in a BFS because we don't want to traverse recursively. We want to traverse one level at a time. So imagine that you visit a vertex v, and then you visit all of v's neighbors w. Now you need to visit each w's neighbors. How are you going to remember all of your w's so that you can go back and visit their neighbors? You're already marked and processed all of the w's. How are you going to find each w's neighbors if you don't remember where the w's are? After all, you're not using recursion, so there's no stack to keep track of them. To perform a BFS, we use a queue. Every time we visit vertex w's neighbors, we dequeue w and enqueue w's neighbors. In this way, we can keep track of which neighbors belong to which vertex. This is the same technique that we saw for the level-order traversal of a tree. The only new trick is that we need to make the vertices, so we don't visit them more than once -- and this isn't even new, since this technique was used for the blobs problem during our discussion of recursion. 

A full N-ary tree has M non-leaf nodes, how many leaf nodes does it have

M + (N ^ (n-1)) = (1 - (N ^ n)) / (1 - N)
Here (N ^ (n-1)) is the number of leaf-nodes.
Solving for this leads to the answer
Leaf nodes = M * (N - 1) + 1

Suppose you have a 3-ary tree

So, here M=4 and N=3.

So using the formula above, Leaf nodes = M * (N - 1) + 1 = 4 * (3 - 1) + 1 = 9 

How many different trees can be constructed using n nodes

Answer is 2^n - n

So, if there are 10 nodes, you will have (1024 - 10) = 1014 different trees! 

What is an AVL tree

AVL trees are self-adjusting, height-balanced binary search trees and are named after the inventors Adelson-Velskii and Landis.

A balanced binary search tree has O(log n) height and hence O(log n) worst case search and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with O (n) height and thus O(n) worst case insertion and lookup times.

AVL trees overcome this problem. An AVL tree is a binary search tree in which every node is height balanced, that is, the difference in the heights of its two subtrees is at most 1. The balance factor of a node is the height of its right subtree minus the height of its left subtree (right minus left!). An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. Each node is associated with a Balancing factor.

Balance factor of each node = height of right subtree at that node - height of left subtree at that node.

Convert a tree into an array

Coming Soon...

Closest ancestor of two nodes in a tree

Coming Soon...

Construct a tree using postorder and preorder traversal

Coming Soon...

Count the number of leaves in a binary tree

Objective: Given the root pointer to a binary tree, find the number of leaves. In the binary tree given below, number of leaf nodes of 4.

Solution: Leaf has property that its left and right child both are null. Using this property we can recurse the tree from root node towards bottom moving to left and right branches and keep counting those nodes which has both the children as null. 

Time Complexity: O(n) where n is number of nodes in the tree.

Java Solution:

       
public class CountNoOfLeaves {

    public static void main(String[] args) throws Exception {
        //Build Tree        
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node7 = new Node(7);
        Node node9 = new Node(9);
        node1.left = node2;
        node1.right = node3;
        node2.left = node7;
        node2.right = node9;
        node3.left = node5;
        node3.right = node4;
        System.out.println(numLeaves(node1));
    }


    private static int numLeaves(Node root){
        if(root == null){
            return 0;
        }

        if(root.left == null && root.right == null){
            return 1;
        }

        return numLeaves(root.left) + numLeaves(root.right);
    }

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

}


 

Delete a node from a Binary Search Tree

Coming Soon...

Level order traversal of a tree

Coming Soon...

Check if a binary tree is a binary search tree

Coming Soon...

Create a copy of a tree

Coming Soon.

Inorder traversal of a binary tree

Inorder tree traversal is a traversal method for binary tree where we traverse left subtree first and then node and right subtree after that. This algorithm can be implemented recursively as well as using iterative method. Following diagram shows inorder traversal:

Recursive algorithm:

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Time Complexity:

Since, we visit every node only once, time complexity is proportional to number of nodes in binary tree.

So, Time Complexity of Inorder traversal is - O(n)

Java Solution:

public class TreeTraversal {

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public void inorder(Node root){
        if(root == null){
            return;
        }
        //Traverse left subtree        

        inorder(root.left);
        System.out.print(root.data + " ");
        //Traverse right subtree        

        inorder(root.right);
    }

    public static void main(String[] args) {
        //Build Tree        

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        new TreeTraversal().inorder(node1);
    }
}

Postorder traversal of a binary tree

Postorder tree traversal is a traversal method for binary tree where we traverse left subtree first and then right subtree and root node after that. This algorithm can be implemented recursively as well as using iterative method. Following diagram shows postorder traversal:

Recursive algorithm:

1. Check if the current node is empty or null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Time Complexity:

Since, we visit every node only once, time complexity is proportional to number of nodes in binary tree.

So, Time Complexity of postorder traversal is - O(n)

public class TreeTraversal {

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public void postorder(Node root){
        if(root == null){
            return;
        }
        //Traverse left subtree        
        postorder(root.left);
        //Traverse right subtree        
        postorder(root.right);
        //Traverse root        
        System.out.print(root.data + " ");
    }

    public static void main(String[] args) {
        //Build Tree        
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        new TreeTraversal().postorder(node1);
    }
}

Preorder traversal of a binary tree

Preorder tree traversal is a traversal method for binary tree where we traverse root first and then left subtree and right subtree after that. This algorithm can be implemented recursively as well as using iterative method. Following diagram shows preorder traversal:

Recursive algorithm:

1. Check if the current node is empty or null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function.

Time Complexity:

Since, we visit every node only once, time complexity is proportional to number of nodes in binary tree.

So, Time Complexity of preorder traversal is - O(n)

Java Solution:

public class TreeTraversal {

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public void preorder(Node root){
        if(root == null){
            return;
        }
        //Traverse root        

        System.out.print(root.data + " ");
        //Traverse left subtree        

        preorder(root.left);
        //Traverse right subtree        

        preorder(root.right);
    }

    public static void main(String[] args) {
        //Build Tree        

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        new TreeTraversal().preorder(node1);
    }
}

Create a mirror copy of a tree

Coming Soon...

Find the maximum depth in a tree

Coming Soon...

Find the minimum value in a binary search tree

Coming Soon...

Determine if two trees are identical

Coming Soon...

Delete a tree and free its nodes

Implementation of deletion of tree and its nodes is largely language dependent. If program is implemented using C/C++, it is program's duty to free up memory so code needs to traverse the tree in postorder fashion and keep freeing the nodes after visiting them.
If the program is implemented in Java, Java itself takes care of freeing up memory as long as object has no hard references pointing to it. Here is the Java solution for deleting a binary tree.

Java Solution:

public class DeleteTree {

    public static void main(String[] args) {
        //Build Tree        

        Node node1= new Node(1);
        Node node2= new Node(2);
        Node node3= new Node(3);
        Node node4= new Node(4);
        Node node5= new Node(5);
        Node node6= new Node(6);
        Node node7= new Node(7);
        Node node8= new Node(8);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node4.left = node8;
        node5.left = node6;
        node6.right = node7;

        deleteTree(node1);
    }


    private static Node deleteTree(Node root){
        if(root == null){
            return null;
        }

        deleteTree(root.left);
        deleteTree(root.right);
        System.out.println("Deleting node:" + root.data);
        root.left = null;
        root.right = null;
        root = null;
        return root;
    }

    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data){
            this.data = data;
        }
    }
}

Determine the number of nodes in a binary tree

In order to find out number of nodes in a tree, we can traverse the tree using any of the traversal method - preorder, inorder and postorder and while traversing we can keep counting the nodes. Solution can be implemented using recursive approach as described earlier as well as using iterative method. In iterative method, we can use level order traversal and keep counting the nodes.
For example, number of nodes in the following binary tree is 9:

Time Complexity: O(n)

Java Recursive Solution:

public class NodeCount {
    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

    public int getNumberOfNodes(Node root){
        if(root == null){
            return 0;
        }

        return 1 + getNumberOfNodes(root.left) + getNumberOfNodes(root.right);
    }

    public static void main(String[] args) {
        //Build Tree

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        System.out.println("Number of nodes in tree are: " + new NodeCount().getNumberOfNodes(node1));
    }
}

Height of a binary tree

Height of a binary tree is 1+ number of edges between root node and a leaf node at longest distance from root node. Descendants of a node is one level deeper than that node. In other words, we need to find out distance from root node to deepest leaf node. Height of empty tree is 0. Height of tree in following tree is 4.

Ways to find out height:

1. Modified level order traversal: We can modify the level order traversal, where we are not just visiting the nodes level by level but we also keep track of level boundary. Total number of levels will be height of the tree.

2. Recursive method: 
In this method, we traverse the tree from root towards leaf recursively. We maintain a counter and increase the counter every time we move one level down. Final count is the height of the tree. Following the java solution for this. Height of the tree in this program is 5:

public class Height {

    public static void main(String[] args) throws Exception {
        //Build Tree        

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node7.right = node9;
        node9.left = node10;
        System.out.println(height(node1));
    }

    private static int height(Node root){
        if(root != null){
            return 1 + max(height(root.left), height(root.right));
        }

        return 0;
    }

    private static int max(int left, int right){
        if(left > right){
            return left;
        }

        return right;
    }
    static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
            this.data = data;
        }
    }

}

Check If a String is a palindrome

Palindrome is a string which which reads the same backward as forward. For example: kayak, rotor, madam, radar, civic etc.

There are various ways to check whether String is a palindrome:

1. Reverse the string and compare: In this approach, we reverse the string and compare it with original string. If these two strings are same, it proves that string is palindrome. Time Complexity of this algorithm is still O(n) but it requires 2n operations (n for reverse and n for comparison)

2. Split the string from middle, reverse second half: In this approach, we form another string by splitting original string from middle to end. After split, we reverse this splitted string. Now, we run a loop to compare original list up to middle element with string formed by split and reverse. If comparison is successful, string is palindrome. It requires n operations (n/2 for split-reverse and n/2 for comparison)

3. Use two pointers: This is the most efficient method out of these three. We take two pointers - one from start of the string and another from end of the string. First pointer moves forward whereas second pointer moves backwards. At every iteration, we check if both the pointers have same character in the string. If both are same, first pointer is moved forward and second pointer is moved backwards. If values are not same, we terminate the loop and declare that string is not a palindrome.
Loop continues until second pointer index becomes lower than first pointer index.

Reverse a Linked List

Objective:
Reverse a linked list.  For example, resulting list after reversing the following list will have nodes in this order -  3, 2, 1.

To reverse a linked list, we need to maintain three pointers prev, current and next. Initially, prev will be pointing to null. We need to traverse through the list and move each pointer one node at a time. In each iteration, we need to unlink current.next from next and point to prev. We need to keep in mind that we need to move next first, so that we don't loose track of next node due to this unlinking. At the end, head will point to the last node in the chain and that way we'll reverse the whole linked list. This algorithm can implemented in iterative as well as recursive fashion.

Following java code gives solution for both the approaches:

Iterative Program:

public class LinkedList {

    Node head;
    Node lastNode;

    public static class Node {
        int data;
        Node next;

        public Node(int data){
            this.data = data;
            this.next = null;
        }
    }

    public void appendNode(int data){

        Node node = new Node(data);

        if(head == null){
            head = node;
            lastNode = head;
        }else {
            lastNode.next = node;
            lastNode = node;
        }
    }

    public void printList(){
        Node temp = head;
        while(temp != null){
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
}

public class ReverseLinkedList {

    private static LinkedList reverseList(LinkedList list) {
        LinkedList.Node prev = null;
        LinkedList.Node temp = list.head;

        while (temp != null) {
            LinkedList.Node current = temp;
            LinkedList.Node next = current.next;
            current.next = prev;
            temp = next;
            prev = current;
        }
        list.head = prev;

        return list;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.appendNode(1);
        list.appendNode(2);
        list.appendNode(3);
        list.appendNode(18);
        list.appendNode(4);
        list.printList();

        LinkedList reverseList = reverseList(list);
        System.out.println();

        list.printList();
    }
}

Recursive Program:

public class ReverseLinkedList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.appendNode(1);
        list.appendNode(2);
        list.appendNode(3);
        list.appendNode(18);
        list.appendNode(4);
        list.printList();

        LinkedList.Node newHead = recursiveReverse(list.head, null);
        list.head = newHead;
        System.out.println();

        list.printList();
    }


    private static LinkedList.Node recursiveReverse(LinkedList.Node head, 

                                                                LinkedList.Node prev) {
        if(head == null){
            return prev;
        }
        LinkedList.Node tmp = head.next;
        head.next = prev;
        return recursiveReverse(tmp, head);
    }
}

Find Loop in a Linked List

While traversing a linked list, when we reach already visited node again it is considered to be a loop in a linked list. We can't reach end of the linked list in case linked list has a loop.
Following diagram shows a linked list with loop. In this diagram, node 6 points back to node 3 which was already visited:

There are various ways to solve this problem:
1. Using HashSet
2. Tortoise Hare algorithm

1. Using HashSet: 

    While traversing the linked list, we insert the node in a HashSet. Every time we visit a node, we check if this node exists in the HashSet. if HashSet already contains this node that means we are visiting this node second time and that proves a cycle in the linked list. Time Complexity of searching in a HashSet is O(1), so time complexity of this algorithm remains O(n) only but it requires O(n) of additional space as well. For a linked list with huge number of nodes, this algorithm is not recommended due to memory requirements.

2. Using Tortoise Hare Algorithm:

This is also known as Floyd's cycle finding algorithm. This is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth. 

Following diagram illustrates this algorithm:

In this algorithm, we maintain two pointers - one is slow pointer and another is fast pointer. Slow pointer is analogy for tortoise and fast pointer is analogous to a hare, that's why algorithm has this name. We start from head node towards the tail. Slow pointer moves one node at a time whereas fast pointer moves two nodes at a time. If there is no loop/cycle in the list, these pointer would never meet. But in case of a cycle, these pointers meet on some node. If these pointers meet it proves a cycle in the list else there is no cycle in the list.

Java Solution:

In this program, we have used three element linked list having nodes 1, 2 and 3. Node 3 points back to node 2.

public class DetectCycle {

    private static void detectLoop(LinkedList.Node head) {
        LinkedList.Node slow = head;
        LinkedList.Node fast = head;

        if (head.next == null) {
            System.out.println("Empty List");
        }

        while (fast != null && slow != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            }
            if (slow == fast) {
                System.out.println("Cycle found in the list");
                return;
            }
        }
        System.out.println("No Cycle found in the list");
    }

    public static void main(String[] args) {
        LinkedList.Node list = getLinkedList();
        detectLoop(list);
    }

    private static LinkedList.Node getLinkedList() {
        LinkedList.Node dummy = new LinkedList.Node(-9999);
        LinkedList.Node head = dummy;
        LinkedList.Node node1 = new LinkedList.Node(1);
        head.next = node1;
        head = head.next;
        LinkedList.Node node2 = new LinkedList.Node(2);
        head.next = node2;
        head = head.next;
        LinkedList.Node node3 = new LinkedList.Node(3);
        node3.next = node2;
        head.next = node3;
        return dummy.next;
    }

    static class LinkedList {
        Node head;

        public static class Node {
            int data;
            Node next;

            public Node(int data) {
                this.data = data;
                this.next = null;
            }
        }
    }
}