import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; // Link each node at each level of tree // Example: // 12 // / \ // 8 20 // / \ / \ // 7 10 14 21 // / \ // 9 15 // // 12 -> null // / \ // 8 -------> 20 -> null // / \ / \ // 7 -> 10 --> 14 -> 21 -> null // / \ // 9 -----> 15 -> null // //public class TreeNode { // public int value; // public TreeNode left; // public TreeNode right; // public TreeNode next; // // public TreeNode(int data) { // value = data; // left = null; // right = null; // next = null; // } //} public class LevelLinking { public static void main(String[] args) { TreeNode root = new TreeNode(12); root.left = new TreeNode(8); root.left.left = new TreeNode(7); root.left.right = new TreeNode(10); root.left.right.left = new TreeNode(9); root.right = new TreeNode(20); root.right.left = new TreeNode(14); root.right.left.right = new TreeNode(15); root.right.right = new TreeNode(21); levelLinkingWithQueue(root); levelLinkingWithList(root); System.out.println(); } public static void levelLinkingWithList(TreeNode root) { TreeNode nullHolder = new TreeNode(0); List result = new ArrayList<>(); result.add(root); result.add(nullHolder); for (int i = 0; i < result.size(); i++) { TreeNode currentNode = result.get(i); if (currentNode == nullHolder && i != result.size() - 1) { result.add(nullHolder); } else { if (currentNode.left != null) { result.add(currentNode.left); } if (currentNode.right != null) { result.add(currentNode.right); } } } for (int i = 0; i < result.size() - 1; i++) { if (result.get(i) != nullHolder && result.get(i + 1) != nullHolder) { result.get(i).next = result.get(i + 1); } } } public static void levelLinkingWithQueue(TreeNode root) { if (root != null) { Queue q = new LinkedList<>(); q.add(root); int currentLevelCounter = 1; int nextLevelCounter = 0; TreeNode prev = null; while (!q.isEmpty()) { TreeNode current = q.poll(); if (current.left != null) { q.offer(current.left); nextLevelCounter++; } if (current.right != null) { q.offer(current.right); nextLevelCounter++; } currentLevelCounter--; if (prev != null) { prev.next = current; } prev = current; if (currentLevelCounter == 0) { currentLevelCounter = nextLevelCounter; nextLevelCounter = 0; prev = null; } } } } }