Home » Binary Tree » Linked List » 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.

in , - on 13:45:00 - No comments

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.   
 
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;
    }
}

Categories: ,

Post a Comment