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.
4. Do recursion keeping the root node as root.right. recursion(root.right).

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);
    }
}

Github :

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));

View on GitHub