DEV Community

Cover image for Leetcode 114. Flatten Binary Tree to Linked List
Rohith V
Rohith V

Posted on

Leetcode 114. Flatten Binary Tree to Linked List

Problem Statement

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.

Test Cases

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Example 2:

Input: root = []
Output: []
Example 3:

Input: root = [0]
Output: [0]

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Algorithm :

  1. Here we need to move all our left child nodes to right and append the already present right child node to the end.
  2. So if we have left child node, first of all store the currently present right child to a variable and keep root.right as the left child. Then make the left child as null.
  3. Then the stored right child is appended towards the end of the left child node that is recently attached. Moving left child to right and appending right child
  4. Do recursion keeping the root node as root.right. recursion(root.right).

Recursively proceeding with right child

Complexity :

We are going through each of the node so time complexity O(n) and space will be O(H) as we use a recursion stack.

Code :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            TreeNode temp = root.right;
            root.right = root.left;
            root.left = null;
            TreeNode current = root.right;
            while (current.right != null) {
                current = current.right;
            }
            current.right = temp;
        }
        flatten(root.right);
    }
}
Enter fullscreen mode Exit fullscreen mode

Github :

GitHub logo Rohithv07 / LeetCode

LeetCode problems that are solved.

LeetCode

LeetCode problems that are solved.

  • take the bit of the ith(from right) digit:

    bit = (mask >> i) & 1;

  • set the ith digit to 1: mask = mask | (1 << i);

  • set the ith digit to 0: mask = mask & (~(1 << i));

A Sample Structure




Top comments (0)