Flatten a binary tree into linked list | Set-3
Given a binary tree, flatten it into linked list in-place. Usage of auxiliary data structure is not allowed. After flattening, left of each node should point to NULL and right should contain next node in level order.
Examples:
Input: 1 / \ 2 5 / \ \ 3 4 6 Output: 1 \ 2 \ 3 \ 4 \ 5 \ 6 Input: 1 / \ 3 4 / 2 \ 5 Output: 1 \ 3 \ 4 \ 2 \ 5
Approach: Recurse the binary tree in Inorder Format, at every stage of function call pass on the address of last node in the flattened linked list so that current node can make itself a right node of the last node.
For left child, it’s parent node is the last node in the flattened list
For the right child there are two conditions:
- If there is no left child to the parent, parent node is the last node in the flattened list.
- If left child is not null then leaf node from left sub-tree is the last node in the flattened list.
Below is the implementation of the above approach:
C++
// C++ program to flatten the binary tree // using previous node approach using namespace std; #include <iostream> #include <stdlib.h> // Structure to represent a node of the tree struct Node { int data; struct Node* left; struct Node* right; }; Node* AllocNode( int data) { Node* temp = new Node; temp->left = NULL; temp->right = NULL; temp->data = data; return temp; } // Utility function to print the inorder // traversal of the tree void PrintInorderBinaryTree(Node* root) { if (root == NULL) return ; PrintInorderBinaryTree(root->left); std::cout << root->data << " " ; PrintInorderBinaryTree(root->right); } // Function to make current node right of // the last node in the list void FlattenBinaryTree(Node* root, Node** last) { if (root == NULL) return ; Node* left = root->left; Node* right = root->right; // Avoid first iteration where root is // the only node in the list if (root != *last) { (*last)->right = root; (*last)->left = NULL; *last = root; } FlattenBinaryTree(left, last); FlattenBinaryTree(right, last); if (left == NULL && right == NULL) *last = root; } // Driver Code int main() { // Build the tree Node* root = AllocNode(1); root->left = AllocNode(2); root->left->left = AllocNode(3); root->left->right = AllocNode(4); root->right = AllocNode(5); root->right->right = AllocNode(6); // Print the inorder traversal of the // original tree std::cout << "Original inorder traversal : " ; PrintInorderBinaryTree(root); std::cout << std::endl; // Flatten a binary tree, at the beginning // root node is the only and last in the list Node* last = root; FlattenBinaryTree(root, &last); // Print the inorder traversal of the flattened // binary tree std::cout << "Flattened inorder traversal : " ; PrintInorderBinaryTree(root); std::cout << std::endl; return 0; } |
Java
// Java program to flatten the binary tree // using previous node approach class GFG { // Structure to represent a node of the tree static class Node { int data; Node left; Node right; }; static Node AllocNode( int data) { Node temp = new Node(); temp.left = null ; temp.right = null ; temp.data = data; return temp; } // Utility function to print the inorder // traversal of the tree static void PrintInorderBinaryTree(Node root) { if (root == null ) return ; PrintInorderBinaryTree(root.left); System.out.print( root.data + " " ); PrintInorderBinaryTree(root.right); } static Node last = null ; // Function to make current node right of // the last node in the list static void FlattenBinaryTree(Node root) { if (root == null ) return ; Node left = root.left; Node right = root.right; // Avoid first iteration where root is // the only node in the list if (root != last) { (last).right = root; (last).left = null ; last = root; } FlattenBinaryTree(left); FlattenBinaryTree(right); if (left == null && right == null ) last = root; } // Driver Code public static void main(String args[]) { // Build the tree Node root = AllocNode( 1 ); root.left = AllocNode( 2 ); root.left.left = AllocNode( 3 ); root.left.right = AllocNode( 4 ); root.right = AllocNode( 5 ); root.right.right = AllocNode( 6 ); // Print the inorder traversal of the // original tree System.out.print( "Original inorder traversal : " ); PrintInorderBinaryTree(root); System.out.println(); // Flatten a binary tree, at the beginning // root node is the only and last in the list last = root; FlattenBinaryTree(root); // Print the inorder traversal of the flattened // binary tree System.out.print( "Flattened inorder traversal : " ); PrintInorderBinaryTree(root); System.out.println(); } } // This code is contributed by Arnab Kundu |
Python
# Python program to flatten binary tree # using previous node approach # Node class to represent a node of the tree class Node: def __init__( self , data): self .data = data self .right = None self .left = None # Utility function to print the inorder # traversal of the tree def PrintInorderBinaryTree(root): if (root = = None ): return PrintInorderBinaryTree(root.left) print ( str (root.data), end = " " ) PrintInorderBinaryTree(root.right) # Function to make current node right of # the last node in the list def FlattenBinaryTree(root): # A global variable which maintains the last node # that was added to the linked list global last if (root = = None ): return left = root.left right = root.right # Avoid first iteration where root is # the only node in the list if (root ! = last): last.right = root last.left = None last = root FlattenBinaryTree(left) FlattenBinaryTree(right) if (left = = None and right = = None ): last = root # Build the tree root = Node( 1 ) root.left = Node( 2 ) root.left.left = Node( 3 ) root.left.right = Node( 4 ) root.right = Node( 5 ) root.right.right = Node( 6 ) # Print the inorder traversal of the # original tree print ( "Original inorder traversal : " , end = "") PrintInorderBinaryTree(root) print ("") # Global variable to maintain the # last node added to the linked list last = root # Flatten the binary tree, at the beginning # root node is the only node in the list FlattenBinaryTree(root) # Print the inorder traversal of the flattened # binary tree print ( "Flattened inorder traversal : " , end = "") PrintInorderBinaryTree(root) # This code is contributed by Pranav Devarakonda |
C#
// C# program to flatten the binary tree // using previous node approach using System; class GFG { // Structure to represent a node of the tree public class Node { public int data; public Node left; public Node right; }; static Node AllocNode( int data) { Node temp = new Node(); temp.left = null ; temp.right = null ; temp.data = data; return temp; } // Utility function to print the inorder // traversal of the tree static void PrintInorderBinaryTree(Node root) { if (root == null ) return ; PrintInorderBinaryTree(root.left); Console.Write(root.data + " " ); PrintInorderBinaryTree(root.right); } static Node last = null ; // Function to make current node right of // the last node in the list static void FlattenBinaryTree(Node root) { if (root == null ) return ; Node left = root.left; Node right = root.right; // Avoid first iteration where root is // the only node in the list if (root != last) { (last).right = root; (last).left = null ; last = root; } FlattenBinaryTree(left); FlattenBinaryTree(right); if (left == null && right == null ) last = root; } // Driver Code public static void Main(String []args) { // Build the tree Node root = AllocNode(1); root.left = AllocNode(2); root.left.left = AllocNode(3); root.left.right = AllocNode(4); root.right = AllocNode(5); root.right.right = AllocNode(6); // Print the inorder traversal of the // original tree Console.Write( "Original inorder traversal : " ); PrintInorderBinaryTree(root); Console.WriteLine(); // Flatten a binary tree, at the beginning // root node is the only and last in the list last = root; FlattenBinaryTree(root); // Print the inorder traversal of the flattened // binary tree Console.Write( "Flattened inorder traversal : " ); PrintInorderBinaryTree(root); Console.WriteLine(); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to flatten the binary tree // using previous node approach // Structure to represent a node of the tree class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } } function AllocNode( data) { var temp = new Node(); temp.left = null ; temp.right = null ; temp.data = data; return temp; } // Utility function to print the inorder // traversal of the tree function PrintInorderBinaryTree( root) { if (root == null ) return ; PrintInorderBinaryTree(root.left); document.write( root.data + " " ); PrintInorderBinaryTree(root.right); } var last = null ; // Function to make current node right of // the last node in the list function FlattenBinaryTree( root) { if (root == null ) return ; var left = root.left; var right = root.right; // Avoid first iteration where root is // the only node in the list if (root != last) { (last).right = root; (last).left = null ; last = root; } FlattenBinaryTree(left); FlattenBinaryTree(right); if (left == null && right == null ) last = root; } // Driver Code // Build the tree var root = AllocNode(1); root.left = AllocNode(2); root.left.left = AllocNode(3); root.left.right = AllocNode(4); root.right = AllocNode(5); root.right.right = AllocNode(6); // Print the inorder traversal of the // original tree document.write( "Original inorder traversal : " ); PrintInorderBinaryTree(root); document.write( "</br>" ); // Flatten a binary tree, at the beginning // root node is the only and last in the list last = root; FlattenBinaryTree(root); // Print the inorder traversal of the flattened // binary tree document.write( "Flattened inorder traversal : " ); PrintInorderBinaryTree(root); document.write( "</br>" ); // This code is contributed by JANA_SAYANTAN. </script> |
Original inorder traversal : 3 2 4 1 5 6 Flattened inorder traversal : 1 2 3 4 5 6
Time Complexity: O(N) where N is the number of nodes in the binary tree.
Auxiliary Space: O(h) where h is the height of binary tree due to recursion call stack.