114. Flatten Binary Tree

Problem Statement

114. Flatten Binary Tree to Linked List - LeetCode

Morris Travel Solution

Morris Traversals of Binary Tree

public void flatten (TreeNode root){
	TreeNode node = root;
	while(node != null) {
		if(node.left != null) { // nodes remaining in left
			// get predecessor
			TreeNode pred = node.left;
			while(pred.right!=null) pred = pred.right;
			// thread and flatten
			pred.right = node.right;
			node.right = node.left;
			node.left = null;
		}
		node = node.right;      // traverse right
	}
}

Reverse Postorder Solution

private TreeNode prev = null;
 
public void flatten(TreeNode root) {
    if (root == null) return;
    
    flatten(root.right);
    flatten(root.left);
    
    // chain prev to the right
    root.right = prev;
    root.left = null;
    
    // update prev
    prev = root;
}

• This solution essentially starts chaining the ‘linked list’ from the end

Without Global Variable

private TreeNode flatten(TreeNode root, TreeNode prev) {
	if (root == null) return prev;
 
	prev = flatten(root.right, prev);
	prev = flatten(root.left, prev);
 
	// chain prev to the right
	root.right = prev;
	root.left = null;
 
	return root;
}
 
 
public TreeNode flatten(TreeNode root) {
	return flatten(root, null);
}