Java/src/BinarySearchTrees/MorrisTraversals.java at master · kasodeep/Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package BinarySearchTrees;

import java.util.ArrayList;
import java.util.List;

/**
 * Crazy Traversal Technique!
 * */
public class MorrisTraversals {

    public static List<Integer> morris(Node root) {
        Node curr = root;
        List<Integer> arr = new ArrayList<>();

        while (curr != null) {
            if (curr.left != null) { // Find Predecessor.
                Node pre = curr.left;
                while (pre.right != null && pre.right != curr) {
                    pre = pre.right;
                }
                if (pre.right == null) { // Connect Predecessor With Current.
                    pre.right = curr;
                    curr = curr.left;
                }
                if (pre.right == curr) { // Unlink Predecessor With Current.
                    pre.right = null;
                    arr.add(curr.val);
                    curr = curr.right;
                }
            } else { // No Predecessor.
                arr.add(curr.val);
                curr = curr.right;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        String[] arr = {"50", "20", "60", "17", "34", "55", "89", "10", "", "28", "", "", "", "70", "", "", "14"};
        Node root = Construct.construct(arr);

        List<Integer> list = morris(root);
        System.out.println(list);
    }
}