Tree height non-recursive version done!

Yay!!! I got rid of the recursion and used an iterative function to calculate height. The trick used was to use a queue. It turned out to be faster and consumed less memory. Fun stuff and I'm happy :)

1 files changed, 47 insertions, 33 deletions

diff --git a/src/main/TreeHeight.java b/src/main/TreeHeight.java
index 0e5119a..f21d607 100644
--- a/src/main/TreeHeight.java
+++ b/src/main/TreeHeight.java
@@ -76,8 +76,8 @@ class TreeHeight {
                 nodes[parentIndex].addChild(nodes[i]);
             }
         }
-//        return treeLevelCounter(nodes, rootIndex);
-        return treeLevelCounterRecursive(nodes[rootIndex]);
+        return treeLevelCounter(nodes, rootIndex);
+//        return treeLevelCounterRecursive(nodes[rootIndex]);
     }
 
     private static int treeLevelCounterRecursive(Node<Integer> node) {
@@ -94,20 +94,33 @@ class TreeHeight {
     }
 
     private static int treeLevelCounter(Node<Integer>[] nodes, int rootIndex) {
-        int levelCounter = 0;
+        int levelCounter = 1;
         Queue<Node<Integer>> q = new LinkedList<>();
-        q.add(nodes[rootIndex]);
+        int popCount = 0;
+        int childrenCount = nodes[rootIndex].getChildren().size();
+        int grandChildrenCount = 0;
+        for (int i = 0; i < childrenCount; i++) {
+            q.add(nodes[rootIndex].getChildren().get(i));
+        }
         while (!q.isEmpty()) {
-            Node<Integer> n = q.remove();
-            int i = n.getChildren().size();
-            if (i != 0) {
-                for (int j = 0; j < i; j++) {
-                    q.add(n.getChildren().get(j));
+            if (popCount < childrenCount) {
+                Node<Integer> n = q.remove();
+                int i = n.getChildren().size();
+                if (i != 0) {
+                    for (int j = 0; j < i; j++) {
+                        q.add(n.getChildren().get(j));
+                    }
                 }
+                grandChildrenCount = grandChildrenCount + i;
+                popCount = popCount + 1;
+            } else {
+                popCount = 0;
+                childrenCount = grandChildrenCount;
+                grandChildrenCount = 0;
+                levelCounter = levelCounter + 1;
             }
-            levelCounter = levelCounter + 1;
         }
-        return levelCounter;
+        return levelCounter + 1;
     }
 
     static int getHeightNaive(int[] a) {
@@ -122,28 +135,7 @@ class TreeHeight {
         return maxHeight;
     }
 
-//    public static void main(String[] args) throws IOException {
-//        FastScanner scanner = new FastScanner(System.in);
-//        int n = scanner.nextInt();
-//        int[] a = new int[n];
-//        for (int i = 0; i < n; i++) {
-//            a[i] = scanner.nextInt();
-//        }
-//        System.out.println(getHeight(a));
-//    }
-    public static void main(String[] args) {
-        new Thread(null, new Runnable() {
-            public void run() {
-                try {
-                    runTheThing();
-                } catch (IOException ignored) {
-                }
-            }
-        }, "1", 1 << 26).start();
-
-    }
-
-    private static void runTheThing() throws IOException {
+    public static void main(String[] args) throws IOException {
         FastScanner scanner = new FastScanner(System.in);
         int n = scanner.nextInt();
         int[] a = new int[n];
@@ -153,4 +145,26 @@ class TreeHeight {
         System.out.println(getHeight(a));
     }
 
+//    public static void main(String[] args) {
+//        new Thread(null, new Runnable() {
+//            public void run() {
+//                try {
+//                    runTheThing();
+//                } catch (IOException ignored) {
+//                }
+//            }
+//        }, "1", 1 << 26).start();
+//
+//    }
+//
+//    private static void runTheThing() throws IOException {
+//        FastScanner scanner = new FastScanner(System.in);
+//        int n = scanner.nextInt();
+//        int[] a = new int[n];
+//        for (int i = 0; i < n; i++) {
+//            a[i] = scanner.nextInt();
+//        }
+//        System.out.println(getHeight(a));
+//    }
+
 }