Create a Linked List of All Nodes at Each Level of Binary Tree Without Using Recursion

Problem

Given a binary tree, create a linked list of all nodes at each level of binary tree without using recursion.

If there are n levels, there will be n linked lists.

You can create an ArrayList of linked lists.

 

Approach

We can use a modified version of BFS.

  1. We will add all elements in a level to a linked list.

  2. Add the current linked list to the arraylist

  3. Save a pointer to the current list as previous list.

  4. Create a new list as current.

  5. Traverse through the previous list and add all the elements to the current list

  6. Repeat from step 2.

 

Solution

ArrayList<LinkedList<TreeNode>> createLists(TreeNode n)

{

  ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();

  if( n== null) return lists;

  LinkedList<TreeNode> currentList = new LinkedList<TreeNode>();

  currentList.add(n);

 

  while( currentList.size() > 0 )

  {

    lists.add(currentList);

    LinkedList<TreeNode> previousList = currentList;

    currentList = new new LinkedList<TreeNode>();

    for( TreeNode p: previousList )

    {

        if( p.left ! = null )

          currentList.add(p.left);

        if( p.right ! = null )

          currentList.add(p.right);

    }

  }

  return lists;

}

 

Complexity

Time complexity is O(n).

Quick Notes Finder Tags

Activities (1) advanced java (1) agile (3) App Servers (6) archived notes (2) ArrayLists (1) Arrays (2) Best Practices (12) Best Practices (Design) (3) Best Practices (Java) (7) Best Practices (Java EE) (1) BigData (3) Chars & Encodings (6) coding problems (2) Collections (15) contests (3) Core Java (All) (53) course plan (2) Database (12) Design patterns (8) dev tools (3) downloads (2) eclipse (9) Essentials (1) examples (14) Exception (1) Exceptions (4) Exercise (1) exercises (6) Getting Started (18) Groovy (2) hadoop (4) hibernate (77) hibernate interview questions (6) History (1) Hot book (4) http monitoring (2) Inheritance (4) intellij (1) java 8 notes (4) Java 9 (1) Java Concepts (7) Java Core (7) java ee exercises (1) java ee interview questions (2) Java Elements (16) Java Environment (1) Java Features (4) java interview points (4) java interview questions (4) javajee initiatives (1) javajee thoughts (3) Java Performance (6) Java Programmer 1 (11) Java Programmer 2 (8) Javascript Frameworks (1) Java SE Professional (1) JSP (1) Legacy Java (1) linked list (3) maven (1) Multithreading (16) NFR (1) No SQL (1) Object Oriented (9) OCPJP (4) OCPWCD (1) OOAD (3) Operators (4) Overloading (2) Overriding (2) Overviews (1) policies (1) programming (1) Quartz Scheduler (1) Quizzes (17) RabbitMQ (1) references (2) resources (1) restful web service (3) Searching (1) security (10) Servlets (8) Servlets and JSP (31) Site Usage Guidelines (1) Sorting (1) source code management (1) spring (4) spring boot (3) Spring Examples (1) Spring Features (1) spring jpa (1) Stack (1) Streams & IO (3) Strings (11) SW Developer Tools (2) testing (1) troubleshooting (1) user interface (1) vxml (8) web services (1) Web Technologies (1) Web Technology Books (1) youtube (1)