Create Linked Lists of all the nodes at each depth in a binary tree.

Create Linked Lists of all the nodes at each depth in a binary tree.

---

Creating linked list of Nodes at same level in a Binary tree is same as printing nodes at each level of a Binary tree with only difference is to collect the Nodes in a list for each level instead of printing it.   

https://javabypatel.blogspot.com/2015/08/binary-tree-traversals-inorder-preorder-postorder-levelorder.html

 
Consider a below Binary Tree,

         50
       /    \
      /      \
     30       70
   /   \     /  \
  20   40   60  80
 /  \
10  25

Output:
50
30 -> 70
20 -> 40 -> 60 -> 80
10 -> 25

Create Linked Lists of all the nodes at each depth in a binary tree.

---

Take 2 queues, one for current level and one for next level.

Put the root node in current level and as we work on current level, we will put left and right child into next level queue as that will be the next level we will be working on.

Once we finish the current level queue, that is where our next level queue is ready to process if it is not empty that would be the case for last level which doesn't has any left/right child.

we initialize currentLevel to nextLevel and repeat the steps.

Create Linked Lists of all the nodes at each depth in a binary tree in Java.

---

package javabypatel.bt;

import java.util.*;

public class LinkedListAtEachDepthOfBinaryTree {
    public static void main(String[] args) {
        Node rootNode = null;
        rootNode = addNode(rootNode, 50);
        rootNode = addNode(rootNode, 30);
        rootNode = addNode(rootNode, 70);
        rootNode = addNode(rootNode, 20);
        rootNode = addNode(rootNode, 40);
        rootNode = addNode(rootNode, 10);
        rootNode = addNode(rootNode, 25);
        rootNode = addNode(rootNode, 60);
        rootNode = addNode(rootNode, 80);

        List<LinkedList<Node>> linkedLists = createLinkedListOfNodesAtEachLevel(rootNode);
    }

    private static List<LinkedList<Node>> createLinkedListOfNodesAtEachLevel(Node root) {
        if (root == null)
            return null;

        List<LinkedList<Node>> linkedLists = new LinkedList<>();

        Queue<Node> currentLevel = new LinkedList<>();
        currentLevel.add(root);
        linkedLists.add(new LinkedList<>());

        Queue<Node> nextLevel = new LinkedList<>();

        while (!currentLevel.isEmpty()) {
            Node node = currentLevel.poll();
            linkedLists.get(linkedLists.size() - 1).add(node);
            System.out.print(node.getData() + ",");

            if (node.getLeft() != null)
                nextLevel.add(node.getLeft());

            if (node.getRight() != null)
                nextLevel.add(node.getRight());

            if (currentLevel.isEmpty() && !nextLevel.isEmpty()) {
                currentLevel = nextLevel;
                nextLevel = new LinkedList<>();
                linkedLists.add(new LinkedList<>());
                System.out.println();
            }
        }
        return linkedLists;
    }

    private static Node addNode(Node rootNode, int i) {
        if (rootNode == null) {
            return new Node(i);
        } else {
            if (i > rootNode.getData()) {
                Node nodeToAdd = addNode(rootNode.getRight(), i);
                rootNode.setRight(nodeToAdd);

            } else {
                Node nodeToAdd = addNode(rootNode.getLeft(), i);
                rootNode.setLeft(nodeToAdd);
            }
        }
        return rootNode;
    }
}

 
package javabypatel.bst;

public class Node {
    private int data;
    private Node left;
    private Node right;

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

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

You may also like to see

---

Advanced Java Multithreading Interview Questions & Answers

Type Casting Interview Questions and Answers In Java?

Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

How is ambiguous overloaded method call resolved in java?

Method Overriding rules in Java

Interface interview questions and answers in Java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Read more

Delete Middle Node of Linked List in Java

Delete Middle Node of Linked List in Java.

---

Given a linked list, Delete the middle node of linked list.

Lets see sample input and output for better understanding:

Read more

Remove duplicates from an unsorted linked list in Java.

Remove duplicates from an unsorted linked list in Java..

---

Given an unsorted linked list, Remove duplicates from it.

Lets see sample input and output for better understanding:

Read more

Check linked list is palindrome or not in java

Check linked list is palindrome or not in Java.

---

A palindromic number is a number that is the same when written forwards or backwards.

Lets see sample input and output for better understanding:

Read more

Delete all occurrences of a given key in a linked list.

Delete all occurrences of a given key in a linked list.

---

Given a Linked list and key to delete, Remove all the occurrences of a given key in singly linked list.

Lets understand what is the input and the expected output.

Read more

Reverse linked list using recursion in Java

Reverse linked list using recursion OR Reverse linked list recursively .

---

Let's see, how to Reverse a linked list recursively in Java

There are 2 ways to Reverse a Linked list using,
1. Recursive Algorithm.
2. Iterative Algorithm.

 Lets understand what is the input and the expected output.

Read more

Java Program for Linear Search.

Java Program for Linear Search.

---

Linear search is a searching algorithm which sequentially searches element in an array.

In this algorithm, elements of array is scanned one by one and check if it is matching with element to search and if found return true else return false.

In last post, we saw how to do Binary search: Binary Search in Java. In this post, we will focus on linear serach.

Lets understand the problem statement graphically and it will be more clear,  

Read more

Print Linked List In Reverse Order in Java

Print Linked List In Reverse Order in Java.

---

Print linked list in reverse order in java. print singly linked list in reverse order using recursion. java program to print linked list in reverse.

Let's understand the problem statement in simple words, 
You are given a Singly linked list, print the linked list in reverse way, from end to start.

Example: 
Input:     10 -> 20 -> 30 -> 40 -> 50 -> null
Output:  50      40     30      20      10
 

Read more

How Floyd's Cycle finding algorithm work

How floyd's cycle-finding algorithm work.

---

How floyd's cycle finding algorithm work in java. Floyd's cycle finding algorithm helps to detect and remove loop in linked list.

What is Loop in Linked list?

Generally, the last node of the linked list points to NULL, which is a indication of end of list.
But in Linked list containing Loop, last node instead of pointing NULL, it points to some of the internal node/starting node/itself.
In this case, If we traverse the Linked list node one by one, our traversal will never ends as it goes in loop.

Check below images for better understanding on how Linked list containing loop looks like.

Read more

Find start node of loop in linked list in Java

Identify start node of loop in Linked list.

---

Find start node of loop in linked list in Java. For identifying start node of cycle in Circular linked list, first detect loop in linked list.
 
Let's begin with, What is Loop in Linked list?

Generally, the last node of the linked list points to NULL, which is a indication of end of list.
But in Linked list containing Loop, last node instead of pointing NULL, it points to some of the internal node/starting node/itself.
In this case, If we traverse the Linked list node one by one, our traversal will never ends as it goes in loop.

Check below images for better understanding on how Linked list containing loop looks like.

Read more

Floyd's Cycle Detection Algorithm in Java

Floyd's Cycle Detection Algorithm in Java. OR
Detect loop in Linked list.

---

Floyd's Cycle Detection Algorithm in Java. Floyd's Cycle finding algorithm helps to detect loop  in linked list. How Floyd's Cycle Algorithm works.
 

Let's start with, What is Loop in Linked list?

Generally, the last node of the linked list points to NULL, which is a indication of end of list.
But in Linked list containing Loop, last node instead of pointing NULL, it points to some of the internal node/starting node/itself.
In this case, If we traverse the Linked list node one by one, our traversal will never ends as it goes in loop.

Check below images for better understanding on how Linked list containing loop looks like.

Read more

Find a Loop in Singly Linked List

Detect loop in Linked list.
Find Cycle in Linked list.
Identify start node of loop in Linked list.
Remove loop in Linked list.

---

Find a Loop in Linked List. To Detect cycle in linked list is popular interview question. Java Program to Detect loop in linked list in Java.

What is Loop in Linked list?

Generally, the last node of the linked list points to NULL, which is a indication of end of list.
But in Linked list containing Loop, last node instead of pointing NULL, it points to some of the internal node/starting node/itself.
In this case, If we traverse the Linked list node one by one, our traversal will never ends as it goes in loop.

Check below images for better understanding on how Linked list containing loop looks like.

Read more

Remove loop from Linked list in Java

Remove loop in Linked list.

---

Remove loop from Linked list in Java. Given a linked list, detect and remove loop in Linked list? Java Program to remove loop in linked list.

Check below images for better understanding on how Linked list containing loop looks like. 

Remove loop in Linked list.

---

Removing the loop in Linked list is simple,

After identifying the loop node, we just require the previous node of loop node, So that we can set it to NULL.

For identifying the previous node of loop node, we will keep the previousPointer pointing to just previous node of loop node.

CASE 2:
When the meeting node of both pointers in loop is start node or root node itself, in this case by just setting previousPointer to NULL will work because previousPointer is already pointing to last node of the linked list.

CASE 1:
When the meeting node of both pointers in loop is in-between the linked list, in this case, first task is to identify the start of loop node in the way as we saw above and then by setting fastPointer, which is already pointing to last node of list to NULL will work.

Program to Remove loop in linked list.

---

package javabypatel;

public class RemoveLoopInLinkList {
 
 Node startNode;
 public static void main(String[] args) {
  RemoveLoopInLinkList g = new RemoveLoopInLinkList();
  
  Node n1 = new Node(10);
  Node n2 = new Node(20);
  Node n3 = new Node(30);
  Node n4 = new Node(40);
  Node n5 = new Node(50);
  Node n6 = new Node(60);
  Node n7 = new Node(70);
  Node n8 = new Node(80);
  
  g.startNode = n1;
  
  n1.setNext(n2);
  n2.setNext(n3);
  n3.setNext(n4);
  n4.setNext(n5);
  n5.setNext(n6);
  n6.setNext(n7);
  n7.setNext(n8);
  n8.setNext(n6);
  
  //Detect and Remove Loop in a Linked List
  Node newStart = detectAndRemoveLoopInLinkedList(g.startNode);
  g.printList(newStart);
 }
 
 private static Node detectAndRemoveLoopInLinkedList(Node startNode) {
  Node slowPointer=startNode;
  Node fastPointer=startNode;
  Node previousPointer=null;
  
  while(fastPointer!=null && fastPointer.getNext()!=null){
   slowPointer = slowPointer.getNext();
   previousPointer = fastPointer.getNext(); // For capturing just previous node of loop node for setting it to null for breaking loop.
   fastPointer = fastPointer.getNext().getNext();
   
   if(slowPointer==fastPointer){ // Loop identified.
    slowPointer = startNode;
 
    //If loop start node is starting at the root Node, then we slowpointer, fastpointer and head all point at same location. 
    //we already capture previous node, just setting it to null will work in this case.
    if(slowPointer == fastPointer){
     previousPointer.setNext(null);
     
    }else{
     // We need to first identify the start of loop node and then by setting just previous node of loop node next to null.  
     while(slowPointer.getNext()!=fastPointer.getNext()){
      slowPointer = slowPointer.getNext();
      fastPointer = fastPointer.getNext();
     }
     fastPointer.setNext(null);
    }
   }
  }
  return startNode; 
 }
 
 //Print linked list.
 private void printList(Node startNode){
  while(startNode!=null){
   System.out.print(startNode.getData() + " " ); 
   startNode=startNode.getNext();
  }
 }
 
}

Read more

Reverse a Linked list in Java Program

Reverse a Linked list OR
Reverse a Singly linked list Iteratively.

---

Let's see, how to Reverse a Singly linked list Iteratively in Java, how to Reverse Linked list using recursion, and how to Reverse a Linked list iteratively.

There are 2 ways to Reverse a Linked list using,
1. Recursive Algorithm.
2. Iterative Algorithm.

 Lets understand what is the input and the expected output.

Read more

Find middle element of a linked list

Find middle element of a linked list in Java

---

Given a singly linked list find middle of the linked list.

Find Nth node from last in a linked list

Lets understand the problem statement graphically and it will be more clear,

Read more

Convert Sorted Linked List to balanced BST

Convert Sorted Linked list to balanced Binary Search Tree

---

Convert sorted list to binary search tree

Lets simplify the question statement, Given a singly Linked List where elements are sorted in  ascending order convert it to a height balanced BST.

A Binary Search Tree is called balanced if the height of left subtree and height of right subtree of Root differ by at most 1.

Lets understand the problem statement graphically and it will be more clear,

Read more

Clone linked list with next and random pointer

Clone linked list with next and random pointer

---

You are given a Doubly Link List with one pointer of each node pointing to the next node just like in a singly link list. The second pointer however can point to any node in the list and not just the previous node.
 
Lets understand the problem statement graphically and it will be more clear,

Read more

Clone Linked list in Java

Copy linked list in Java

---

Given a Linked list, Create a deep copy of Linked list.

Lets understand the problem statement graphically and it will be more clear,

Read more

Sort Linked list using Merge sort.

Sort Linked List using Merge Sort.

---

Given a Linked list, Sort it using Merge Sort Algorithm.

Merge sort is preferred algorithm for sorting a linked list, lets see why,
The way linked list is structured which doesn't allow random access makes some other algorithms like Quicksort perform poorly, So Merge sort is often preferred algorithm for sorting linked list.
 
Lets understand what is the input and the expected output.

Read more

Find Nth node from last in a linked list

Find Nth node from last in a linked list

---

Lets understand what is the input and the expected output.


Find middle element of the Linked list

Read more