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.

Problem

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

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

You can create an ArrayList of linked lists.

Approach

We will create an ArrayList of linked lists. We will pass in the array list to the method along with a level attribute. 

If the size of arraylist is equal to the level, the level has not been visited before and we will create a new linked list and add elements.

Approach 

Recursively substract the data values of child nodes from current node.

Assume the full and complete tree with levels as:

6

11

1111

This will become 6 - (1-1-1) - (1-1-1) => 6 - (-1) - (-1) => 6+1 + 1 => 8.

Solution

int getLevelDiff(TreeNode n)
{
  if(n==null) return 0;
  
  return (n.data - getLevelDiff(n.left) - getLevelDiff(n.right));
}

In this solution we will be using only one stack.

Solution

void postorder(TreeNode n)

{

  if (n == null) return;

 

  TreeNode current = n;

  Stack s = new Stack();

  do{

  while(current!=null)

  {

    if(current.right!=null) s.push(current.right);

    s.push(current);

    current = current.left;

  }

  if(current.right ! = null && current.right == stack.peep())

  { //swap them

    stack.pop();

    stack.push(current);

Approach

We can do post order traversal iteratively using two stacks.

There are also approaches involving one stack, but this seems to be a simpler one to understand.

For a root element T1 with left child T2 and right child T3, post order traversal order will be T2, T3, and T1.

To make this happen, we should elements in the order T1, T2 and T3 into the second stack and then print them.

Approach can be summarized as:

• Create two stacks s1 and s2.

• Push root to first stack s1.