Flatten Binary Tree to Linked List Editorial

Practice Problem Link: Flatten Binary Tree to Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a binary tree, flatten it to a linked list.

Flattening a binary tree means that:

• All the right pointers should point to the next node.
• All the left pointers should point to null.
• The linked list should be in the same order as the preorder traversal of the tree.

Approach

Since the linked list should be in the preorder traversal of the tree, the idea is to flatten the given tree recursively by doing reverse preorder traversal. i.e.

• Flatten the right subtree.
• Flatten the left subtree.
• Flatten the current node.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
Node* prevNode;
void flattenTree(Node *root) {
	if (root == NULL) {
		return;
	}
	flattenTree(root->right);
	flattenTree(root->left);
	root->right = prevNode;
	root->left = NULL;
	prevNode = root;
}
void flatten(Node* root) {
    prevNode = NULL;
	flattenTree(root);
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	Node prevNode;
	void flattenTree(Node root) {
		if (root == null) {
			return;
		}
		flattenTree(root.right);
		flattenTree(root.left);
		root.right = prevNode;
		root.left = null;
		prevNode = root;
	}
	void flatten(Node root) {
    	prevNode = null;
		flattenTree(root);
	}
}