Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree

Question

I have to solve the following problem: Given a perfect binary tree, that stores characters on its nodes, reverse the nodes on the odd levels. The problem and the solution are taken from here: http://www.geeksforgeeks.org/reverse-alternate-levels-binary-tree/.

I am trying to implement the tricky solution. This is my code:

  import java.util.ArrayList;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Queue;


  public class ReverseLevel {
   public static class Node{
    char id;
    Node left;
    Node right;
    public Node(char id){
        this.id = id;
        left = null;
        right = null;
    }
}
static Node root;
static Queue<Node> q;
static int index;
static List<Character> res = new ArrayList<Character>();
public static void main(String[] args) {
    createBT();
    printLevelbyLevel(root);
    reverseLevels(root, 0);
    int n = res.size();
    System.out.println();
    for (int i = 0; i < n; i++) {
        System.out.print(res.get(i) + " ");
    }
    System.out.println();
    setLevels(root, 0, n-1);
    printLevelbyLevel(root);

}
private static void printLevelbyLevel(Node root2) {
    q = new LinkedList<Node>();
    q.add(root);
    Queue<Node> nextLevel = new LinkedList<Node>();
    while(!q.isEmpty()){
        Node n = q.remove();
        printNode(n);
        if(hasLeftChild(n)){
            nextLevel.add(n.left);
        }
        if(hasRightChild(n)){
            nextLevel.add(n.right);
        }
        if(q.isEmpty()){
            System.out.println();
            while(!nextLevel.isEmpty()){
                q.add(nextLevel.poll());
            }
        }
    }
}
private static void reverseLevels(Node root, int level){
    if(root == null){
        return;
    }
    reverseLevels(root.left, level+1);
    if(level%2 == 1){
        res.add(root.id);
    }
    reverseLevels(root.right, level+1);

}
private static void setLevels(Node root, int level, int index){
    if(root == null){
        return;
    }
    setLevels(root.left, level+1, index);
    if(level%2 == 1){
        root.id = res.get(index);
        index--;
    }
    setLevels(root.right, level+1, index);
}


private static boolean hasRightChild(Node n) {
    if(n.right != null)
        return true;
    return false;
}
private static boolean hasLeftChild(Node n) {
    if(n.left != null)
        return true;
    return false;
}
private static void printNode(Node n) {
    System.out.print(n.id + " ");
}
private static void createBT() {
    Node n1 = new Node('a');
    Node n2 = new Node('b');
    Node n3 = new Node('c');
    Node n4 = new Node('d');
    Node n5 = new Node('e');
    Node n6 = new Node('f');
    Node n7 = new Node('g');
    Node n8 = new Node('h');
    Node n9 = new Node('i');
    Node n10 = new Node('g');
    Node n11 = new Node('k');
    Node n12 = new Node('l');
    Node n13 = new Node('m');
    Node n14 = new Node('n');
    Node n15 = new Node('o');
    root = n1;
    n1.left = n2;
    n1.right = n3;
    n2.left = n4;
    n2.right = n5;
    n4.left = n8;
    n4.right = n9;
    n5.left = n10;
    n5.right = n11;
    n3.left = n6;
    n3.right = n7;
    n6.left = n12;
    n6.right = n13;
    n7.left = n14;
    n7.right = n15;
}

}

The idea is to traverse the tree in-order fashion, store the nodes from odd levels in an ArrayList res and then again traverse the tree in in-order fashion and for each node which is in odd level, I replace its id by the corresponding value in res. While the second in-order traversal, I keep field index, which tells me from which index of res I should take my data.

Whenever I replace the data in the corresponding node with that from res, I decrement index. However since it is a recursion, if I go in upper levels of the recursion, the value of index gets the same as before, and I don't change the data of the nodes correctly. Can someone suggest me how can I avoid this? I have included methods for printing the tree level by level, so it is visible that the method doesn't work correctly.

Answer 1

Use Collections.reverse(res) after calling reverseLevels(). This will reverse your ArrayList.

In the function setLevels() instead of below code

if(level%2 == 1)
{
   root.id = res.get(index);
   index--;
}

use below snippet. Then there will be no need to use index as the element you want is the first element and you remove it.

if(level%2 == 1)
{
   root.id = res.get(0);
   res.remove(0);
}

Answer 2

You should use a java.util.Stack to push and pop the nodes. Here is a modified version of your code:

public class ReverseLevel {
    public static class Node {
        char id;
        Node left;
        Node right;

        public Node(char id) {
            this.id = id;
            left = null;
            right = null;
        }
    }

    static Node            root;
    static Queue<Node>     q;
    static int             index;
    static Stack<Character> stack = new Stack<Character>();

    public static void main(String[] args) {
        createBT();
        printLevelbyLevel(root);

        reverseLevels(root, 0);

        setLevels(root, 0);
        printLevelbyLevel(root);

    }

    private static void printLevelbyLevel(Node root2) {
        q = new LinkedList<Node>();
        q.add(root);
        Queue<Node> nextLevel = new LinkedList<Node>();
        while (!q.isEmpty()) {
            Node n = q.remove();
            printNode(n);
            if (hasLeftChild(n)) {
                nextLevel.add(n.left);
            }
            if (hasRightChild(n)) {
                nextLevel.add(n.right);
            }
            if (q.isEmpty()) {
                System.out.println();
                while (!nextLevel.isEmpty()) {
                    q.add(nextLevel.poll());
                }
            }
        }
    }

    private static void reverseLevels(Node root, int level) {
        if (root == null) {
            return;
        }
        reverseLevels(root.left, level + 1);
        if (level % 2 == 1) {
            stack.push(root.id);
        }
        reverseLevels(root.right, level + 1);

    }

    private static void setLevels(Node root, int level) {
        if (root == null) {
            return;
        }
        setLevels(root.left, level + 1);
        if (level % 2 == 1) {
            root.id = stack.pop();
        }
        setLevels(root.right, level + 1);
    }

    private static boolean hasRightChild(Node n) {
        if (n.right != null)
            return true;
        return false;
    }

    private static boolean hasLeftChild(Node n) {
        if (n.left != null)
            return true;
        return false;
    }

    private static void printNode(Node n) {
        System.out.print(n.id + " ");
    }

    private static void createBT() {
        Node n1 = new Node('a');
        Node n2 = new Node('b');
        Node n3 = new Node('c');
        Node n4 = new Node('d');
        Node n5 = new Node('e');
        Node n6 = new Node('f');
        Node n7 = new Node('g');
        Node n8 = new Node('h');
        Node n9 = new Node('i');
        Node n10 = new Node('g');
        Node n11 = new Node('k');
        Node n12 = new Node('l');
        Node n13 = new Node('m');
        Node n14 = new Node('n');
        Node n15 = new Node('o');
        root = n1;
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n4.left = n8;
        n4.right = n9;
        n5.left = n10;
        n5.right = n11;
        n3.left = n6;
        n3.right = n7;
        n6.left = n12;
        n6.right = n13;
        n7.left = n14;
        n7.right = n15;
    }
}

Answer 3

I'll admit i havent read the your program, what caught me was that you mentioned odd levels and you are doing inorder traversal.Thats quiet odd for me!

If i would code this, here would be my approach :

• if i have to work on level's in BST, i'll go with level-order-traversal (BFS simply) and keep a track of odd levels.

• Then,on every odd level, on deQueueing a value of a node, i'll swap it with the current node value. (that's it!!)

This is more space efficient (no stack space needed) and is achieved in O(n) time

Example :

              10             //Level 0
            /    \
           5      20         //Level 1
         /   \  /   \
        1    3 12   25       //Level 2

When enQueued for Level-1, You will have 5 in deQueue and 20 at the front of Queue.

Now, just check if the level is odd.If yes, then swap the deQueueed value with the value of node in the front!

5<=>20 in this case