114. Flatten Binary Tree to Linked List Leetcode Solution
Flatten Binary Tree to Linked List Leetcode Problem :
Given the root of a binary tree, flatten the tree into a “linked list”:
The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.
Flatten Binary Tree to Linked List Leetcode Solution :
Constraints :
- The number of nodes in the tree is in the range [0, 2000].
- -100 <= Node.val <= 100
Example 1:
- Input: root = []
- Output: []
Example 2:
- Input: root = [0]
- Output: [0]
Intuition :
We need to remember the tail of the linked list we have created so that we don’t traverse the end of the list to attach the root’s right node again and I observed it was always the last leaf node that we have found during traversal so I stored it.
Approach :
We do inorder traversal. Incase a leaf node is found I store in in store variable. I call the function with the root’s left node if present. After that in case there is value of store is not null then I do the following operation:
1)Store root’s right node
2)Make root’s left node as root’s right node
3)The tail of the left subtree linked list is stored in store so I make the original root’s right node as store’s right node.
After this I call the function on original root’s right node.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
void helper(TreeNode* root,TreeNode* &store){
if(root->left==NULL && root->right==NULL){
store=root;
return;
}
if(root->left){
helper(root->left,store);
}
TreeNode* temp=root->right;
if(store!=NULL){
root->right=root->left;
store->right=temp;
}
root->left=NULL;
if(temp){
store=NULL;
helper(temp,store);
}
}
void flatten(TreeNode* root) {
if(root==NULL || (root->left==NULL && root->right==NULL)){
return;
}
TreeNode* store=NULL;
helper(root,store);
}
};
class Solution {
public void flatten(TreeNode root) {
if(root==null)
return;
Stack stack = new Stack<>();
while(true){
if(root.right != null)
stack.push(root.right);
if(root.left==null){
if(stack.isEmpty())
break;
root.right = stack.pop();
}
else{
root.right = root.left;
root.left = null;
}
root = root.right;
}
return;
}
}
class Solution:
def __init__(self):
self.prev=None
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root: return
self.flatten(root.right)
self.flatten(root.left)
root.right=self.prev
root.left=None
self.prev=root
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment