Node To Root Path In Generic Tree

I/P:

24 10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1 120

O/P:

[120, 80, 30, 10]

package pep.Day29;

import java.io.*;
import java.util.*;

public class Node_To_Root_Path_In_GenericTree {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);
        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static ArrayList<Integer> nodeToRootPath(Node node, int data) {
        if (node.data == data) {
            ArrayList<Integer> base = new ArrayList<>();
            base.add(data);
            return base;
        }
        for (Node child : node.children) {
            ArrayList<Integer> pathTillChild = nodeToRootPath(child, data);
            if (pathTillChild.size() > 0) {
                pathTillChild.add(child.data);
                return pathTillChild;
            }
        }

        return new ArrayList<Integer>();
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }
        int data = Integer.parseInt(br.readLine());
        Node root = construct(arr);
        ArrayList<Integer> path = nodeToRootPath(root, data);
        System.out.println(path);
        // display(root);
    }

}

Find In Generic Tree

I/P:

24

10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

100

O/P: true

1• First of all we check the data of the node at which we are standing. 

2• If the data matches the data of the node then we return true from here only. No further statement will run in such a case. 

3• A for loop is applied to access all the children of Node node one by one. 

4• Inside this for loop, we make a recursive call to each child until we find the data and store this result in variable fic (find in child). 

5• We check if this variable is true. It means that data was present in the child branch to which the last call was made. 

6• So we return true because there is no need to make further calls. As we have found the data. 

7• If fic were false then control comes out of the for loop and we return false.

package pep.Day29;

import java.io.*;
import java.util.*;

public class Find_In_GenericTrees {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static boolean find(Node node, int data) {
        if (node.data == data)
            return true;

        // faith: mere children yhe btae ki unme hai ya nhi
        for (Node child : node.children) {
            boolean bool = find(child, data);
            if (bool) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        int data = Integer.parseInt(br.readLine());

        Node root = construct(arr);
        boolean flag = find(root, data);
        System.out.println(flag);
        // display(root);
    }

}

Linearize A Generic Tree | Efficient Approach - O(n)

I/P: 

24

10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

O/P:

10 -> 20, .

20 -> 50, .

50 -> 60, .

60 -> 30, .

30 -> 70, .

70 -> 80, .

80 -> 110, .

110 -> 120, .

120 -> 90, .

90 -> 40, .

40 -> 100, .

100 -> .

FAITH: Linearize method, linear bhi krega and tail bhi laakr dega

package pep.Day29;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Linearize_A_GenericTree_EfficientWay {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static Node linearize(Node node) {
        // woh khud ek leaf node hai, islea vhi return kr do
        // node.children.size() = 0 ho gya to, node.children.size() - 1 = -ve aaega
        if (node.children.size() == 0)
            return node;

        Node lastNode = node.children.get(node.children.size() - 1);
        // last ki tail mil gae, also, last linearize bhi ho gya
        Node lastNode_Tail = linearize(lastNode);

        while (node.children.size() > 1) {
            Node last = node.children.remove(node.children.size() - 1);
            Node secondLast = node.children.get(node.children.size() - 1);

            // second last ki tail mil gae, also, linearize bhi ho gya
            Node secondLastNode_Tail = linearize(secondLast);
            secondLastNode_Tail.children.add(last);
        }
        return lastNode_Tail;
    }

    private static Node getTail(Node node) {
        while (!node.children.isEmpty())
            node = node.children.get(0);
        return node;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }
        Node root = construct(arr);
        linearize(root);
        display(root);
    }

}

Linearize A Generic Tree - O (n ^ 2)

I/P: 

24

10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

O/P:

10 -> 20, .

20 -> 50, .

50 -> 60, .

60 -> 30, .

30 -> 70, .

70 -> 80, .

80 -> 110, .

110 -> 120, .

120 -> 90, .

90 -> 40, .

40 -> 100, .

100 -> .

1. Sab apne apne child pehle linearize kr kr le aaenge

2. ag kise ke paas bhi e se jyada child hai to, usko linear bna denge

package pep.Day29;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Linearize_A_GenericTree {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static void linearize(Node node) {
        for (Node child : node.children) {
            linearize(child);
        }
        while (node.children.size() > 1) {
            // last node ko remove kr denge using (node.children.size() - 1)
            Node lastNode = node.children.remove(node.children.size() - 1);

            // last node ko get kr denge using (node.children.size() - 1)
            Node secondLastNode = node.children.get(node.children.size() - 1);

            // jo last node bache hai after deletion, uski lat node laaenge
            getTail(secondLastNode).children.add(lastNode);
        }
    }

    private static Node getTail(Node node) {
        while (!node.children.isEmpty())
            node = node.children.get(0);
        return node;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }
        Node root = construct(arr);
        linearize(root);
        display(root);
    }

}

1. Time Complexity: O(n^2)

We have visited every node to linearize it. Although the leaf nodes do not get linearized, still we have visited them and so, we have visited n nodes. Also, when we visit them and try to linearize them, we visit all the nodes after linearizing in order to find the tail and add the next node in the pre-order to its children's ArrayList. This happens inside the first loop of traversal. So, in a way- we have a nested loop where we are visiting almost n elements every time. So, the time complexity is O(n^2).

after recursion, in post order we have another another loop to getTain by traversing n elements.

2. Space Complexity: O(1)

The space complexity remains O(1) since we haven't used any extra space.

Remove Leaves In Generic Tree

I:P:

24 10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

O/P:

10 -> 20, 30, 40, . 20 -> . 30 -> 80, . 80 -> . 40 -> .

package pep.Day29;

import java.io.*;
import java.util.*;

public class Remove_Leaves_In_GenericTree {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static int size(Node node) {
        int s = 0;

        for (Node child : node.children) {
            s += size(child);
        }
        s += 1;

        return s;
    }

    public static int max(Node node) {
        int m = Integer.MIN_VALUE;

        for (Node child : node.children) {
            int cm = max(child);
            m = Math.max(m, cm);
        }
        m = Math.max(m, node.data);

        return m;
    }

    public static int height(Node node) {
        int h = -1;

        for (Node child : node.children) {
            int ch = height(child);
            h = Math.max(h, ch);
        }
        h += 1;

        return h;
    }

    public static void traversals(Node node) {
        System.out.println("Node Pre " + node.data);

        for (Node child : node.children) {
            System.out.println("Edge Pre " + node.data + "--" + child.data);
            traversals(child);
            System.out.println("Edge Post " + node.data + "--" + child.data);
        }

        System.out.println("Node Post " + node.data);
    }

    public static void levelOrderLinewiseZZ(Node node) {
        Stack<Node> stack = new Stack<>();
        stack.add(node);

        Stack<Node> cstack = new Stack<>();
        int level = 0;

        while (stack.size() > 0) {
            node = stack.pop();
            System.out.print(node.data + " ");

            if (level % 2 == 0) {
                for (int i = 0; i < node.children.size(); i++) {
                    Node child = node.children.get(i);
                    cstack.push(child);
                }
            } else {
                for (int i = node.children.size() - 1; i >= 0; i--) {
                    Node child = node.children.get(i);
                    cstack.push(child);
                }
            }

            if (stack.size() == 0) {
                stack = cstack;
                cstack = new Stack<>();
                level++;
                System.out.println();
            }
        }
    }

    public static void mirror(Node node) {
        for (Node child : node.children) {
            mirror(child);
        }
        Collections.reverse(node.children);
    }

    public static void removeLeaves(Node node) {
        // jine child ke children nhi hai
        // remove them
        for (int i = node.children.size() - 1; i >= 0; i--) {
            Node child = node.children.get(i);
            if (child.children.isEmpty())
                node.children.remove(i);
        }

        // make recursive call for all child
        for (Node child : node.children) {
            removeLeaves(child);
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        Node root = construct(arr);
        removeLeaves(root);
        display(root);
    }

}

Time Complexity: We are traversing all the nodes once, hence the time complexity will be O(n) where n = number of nodes in the generic tree. 

Space Complexity: We are not using any extra space in the form of any auxiliary data structure. Hence the space complexity is O(1). Note: We are using recursion which does take stack space of O(d) where d = maximum depth of the generic tree.

Mirror Of A Generic Tree

I/P:

24 10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

O:P:

10 -> 20, 30, 40, . 20 -> 50, 60, . 50 -> . 60 -> . 30 -> 70, 80, 90, . 70 -> . 80 -> 110, 120, . 110 -> . 120 -> . 90 -> . 40 -> 100, . 100 -> .

10 -> 40, 30, 20, . 40 -> 100, . 100 -> . 30 -> 90, 80, 70, . 90 -> . 80 -> 120, 110, . 120 -> . 110 -> . 70 -> . 20 -> 60, 50, . 60 -> . 50 -> .

package pep.Day29;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class Mirror_A_GenericTree {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static void mirror(Node node) {
        // faith: each children will bring the reverse child of their own
        for (Node child : node.children)
            mirror(child);
        // expectation meet faith: reverse the childern arraylist 
        Collections.reverse(node.children);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        Node root = construct(arr);
        display(root);
        mirror(root);
        display(root);
    }

}

Time Complexity: O(n) The time complexity for the function is linear as we post traversing the tree.

Space Complexity: O(nlogn) The space complexity for the function is equal to the height of the tree due to the recursion stack.

Level Order Traversal - Line Wise 4 : Using Pair class

I/P:

24

10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

O/P:

10 

20 30 40 

50 60 70 80 90 100 

110 120 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Stack;

public class LevelOrder_Linewise_Of_GenericTree_4 {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);
        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static int size(Node node) {
        int s = 0;

        for (Node child : node.children) {
            s += size(child);
        }
        s += 1;

        return s;
    }

    private static class Pair {
        Node node;
        int level;

        Pair(Node node, int level) {
            this.node = node;
            this.level = level;
        }
    }

    public static void levelOrderLinewise(Node node) {
        Queue<Pair> mainQueue = new ArrayDeque<>();
        int level = 1;
        mainQueue.add(new Pair(node, level));

        while (!mainQueue.isEmpty()) {
            Pair pair = mainQueue.remove();
            if (pair.level > level) {
                level = pair.level;
                System.out.println();
            }
            System.out.print(pair.node.data + " ");

            for (Node child : pair.node.children) {
                Pair childPair = new Pair(child, level + 1);
                mainQueue.add(childPair);
            }
        }
    }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        Node root = construct(arr);
        levelOrderLinewise(root);
    }

}

Level Order Traversal - Line Wise 3 : Using 2 queue mainQueue, childQueue

I/P:

24

10 20 50 -1 60 -1 -1 30 70 -1 80 110 -1 120 -1 -1 90 -1 -1 40 100 -1 -1 -1

O/P:

10 

20 30 40 

50 60 70 80 90 100 

110 120 

package pep.Day28;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Stack;

public class LevelOrder_Linewise_Of_GenericTree_3 {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child : node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);
        for (Node child : node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static int size(Node node) {
        int s = 0;

        for (Node child : node.children) {
            s += size(child);
        }
        s += 1;

        return s;
    }

    public static void levelOrderLinewise(Node node) {
        // write your code here

        Queue<Node> mainQueue = new ArrayDeque<>();
        Queue<Node> childQueue = new ArrayDeque<>();

        mainQueue.add(node);
        while (!mainQueue.isEmpty()) {
            // remove
            Node out = mainQueue.remove();
            // print
            System.out.print(out.data + " ");

            // add children
            // for left to right printing of node
            for (Node child : out.children)
                childQueue.add(child);

            // swaping of mainStack and childStack.
            // also, incrementing the level
            if (mainQueue.isEmpty()) {
                mainQueue = childQueue;
                childQueue = new ArrayDeque<>();
                System.out.println();
            }
        }


    }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        Node root = construct(arr);
        levelOrderLinewise(root);
    }

}