Flatten Binary Tree
Category: Binary Trees
```
Problem Statement
Flatten Binary Tree Write a function that takes in a Binary Tree, attens it, and returns its leftmost node. A attened Binary Tree is a structure that's nearly identical to a Doubly Linked List (except that nodes have left and right pointers instead of prev and next pointers), where nodes follow the original tree's left-to-right order. Note that if the input Binary Tree happens to be a valid Binary Search Tree, the nodes in the attened tree will be sorted. The attening should be done in place, meaning that the original data structure should be mutated (no new structure should be created). Each BinaryTree node has an integer value , a left child node, and a right child node. Children nodes can either be BinaryTree nodes themselves or None / null . Sample Input tree = 1 / \ 3 / \ / 5 6 / \ 8 Sample Output <-> 2 <-> 7 <-> 5 <-> 8 <-> 1 <-> 6 <-> 3 // the leftmost node with value 4 Hints Hint 1 You can solve this problem pretty easily by traversing the tree using the in-order tree-traversal technique, gathering all of the nodes in an array, and then iterating through them from left to right and connecting them accordingly. Can you solve this problem without storing an entire array of the tree's nodes? Hint 2 Try to gure out what the relation between two adjacent nodes in the in-order-traversal order is, as far as positioning in the tree is concerned. Hint 3 At any given node in the in-order-traversal order, the node immediately to its left is the rightmost node of its left subtree, and the node immediately the its right is the leftmost node of its right subtree. Hint 4 Write a function that recursively gets the leftmost and rightmost nodes of a given node's left subtree and right subtree and that connects the left subtree's rightmost node to the given node and the right subtree's leftmost node to the given node. Optimal Space & Time Complexity O(n) time | O(d) space - where n is the number of nodes in the Binary Tree and d is the depth (height) of the Binary Tree
```
Approach & Solution
Solution 1
``` Solution 1 Solution 2 import java.util.*; class Program { // O(n) time | O(d) space - where n is the number of nodes in the Binary Tree // and d is the depth (height) of the Binary Tree public static BinaryTree flattenBinaryTree(BinaryTree root) { flattenTree(root); return getLeftMost(root); } public static BinaryTree[] flattenTree(BinaryTree node) { BinaryTree leftMost; BinaryTree rightMost; if (node.left == null) { leftMost = node; } else { BinaryTree[] leftAndRightMostNodes = flattenTree(node.left); connectNodes(leftAndRightMostNodes[1], node); leftMost = leftAndRightMostNodes[0]; } if (node.right == null) { rightMost = node; } else { BinaryTree[] leftAndRightMostNodes = flattenTree(node.right); connectNodes(node, leftAndRightMostNodes[0]); rightMost = leftAndRightMostNodes[1]; } return new BinaryTree[] {leftMost, rightMost}; } public static void connectNodes(BinaryTree left, BinaryTree right) { left.right = right; right.left = left; } public static BinaryTree getLeftMost(BinaryTree node) { while (node.left != null) { node = node.left; } return node;
Solution 2
```
Solution 1 Solution 2
2
3 import java.util.*;
4
5 class Program {
6 // O(n) time | O(n) space - where n is the number of nodes in the Binary Tree
7 public static BinaryTree flattenBinaryTree(BinaryTree root) {
8 List
```
Test Cases
``` Hide
``` Test Case 1 { "tree": { "nodes": [ {"id": "1", "left": "2", "right": "3", "value": 1}, {"id": "3", "left": "6", "right": null, "value": 3}, {"id": "6", "left": null, "right": null, "value": 6}, {"id": "2", "left": "4", "right": "5", "value": 2}, {"id": "5", "left": "7", "right": "8", "value": 5}, {"id": "8", "left": null, "right": null, "value": 8}, {"id": "7", "left": null, "right": null, "value": 7}, {"id": "4", "left": null, "right": null, "value": 4} ], "root": "1" } } Test Case 2 { "tree": { "nodes": [{"id": "1", "left": null, "right": null, "value": 1}], "root": "1" } } Test Case 3 { "tree": { "nodes": [ {"id": "1", "left": "2", "right": null, "value": 1}, {"id": "2", "left": null, "right": null, "value": 2} ], "root": "1" } } Test Case 4 { "tree": { "nodes": [ {"id": "1", "left": "2", "right": "3", "value": 1}, {"id": "3", "left": null, "right": null, "value": 3}, {"id": "2", "left": null, "right": null, "value": 2} ], "root": "1" } } Test Case 5 { "tree": { "nodes": [ {"id": "1", "left": "2", "right": "3", "value": 1}, {"id": "3", "left": null, "right": null, "value": 3}, {"id": "2", "left": "4", "right": null, "value": 2}, {"id": "4", "left": null, "right": null, "value": 4} ], "root": "1" } } Test Case 6 { "tree": { "nodes": [ {"id": "1", "left": "2", "right": "3", "value": 1}, {"id": "3", "left": null, "right": null, "value": 3}, {"id": "2", "left": "4", "right": "5", "value": 2}, {"id": "5", "left": null, "right": null, "value": 5}, {"id": "4", "left": null, "right": null, "value": 4} ], "root": "1" } } Test Case 7 { "tree": { "nodes": [ {"id": "1", "left": "2", "right": "3", "value": 1}, {"id": "3", "left": "6", "right": null, "value": 3}, {"id": "6", "left": null, "right": null, "value": 6}, {"id": "2", "left": "4", "right": "5", "value": 2}, {"id": "5", "left": null, "right": null, "value": 5}, {"id": "4", "left": null, "right": null, "value": 4} ], "root": "1" } } Test Case 8 { "tree": { "nodes": [ {"id": "1", "left": "2", "right": "3", "value": 1}, {"id": "3", "left": "6", "right": "7", "value": 3}, {"id": "7", "left": null, "right": null, "value": 7}, {"id": "6", "left": "12", "right": null, "value": 6}, {"id": "12", "left": null, "right": null, "value": 12}, {"id": "2", "left": "4", "right": "5", "value": 2}, {"id": "5", "left": "10", "right": "11", "value": 5}, {"id": "11", "left": null, "right": null, "value": 11}, {"id": "10", "left": null, "right": null, "value": 10}, {"id": "4", "left": "8", "right": "9", "value": 4}, {"id": "9", "left": null, "right": null, "value": 9}, {"id": "8", "left": null, "right": null, "value": 8} ], "root": "1" } }