Right Sibling Tree

Category: Binary Trees

```

Problem Statement

Sample Input tree = 1 / \ 3 / \ / \ 5 6 7 / \ \ / / \ 9 10 11 12 13 / Sample Output // the root node with value 1 / 2-----------3 / / 4-----5-----6-----7 / / / 8---9 10-11 12-13 // the node with value 10 no longer has a node pointing to it / Hints Hint 1 Try to identify a pattern or formula that determines how to reach a given node's right sibling. Hint 2 There are two patterns: if a node is the left child of another node, its right sibling is its parent's right child; if a node is the right child of another node, its right sibling is its parent's right sibling's left child. Hint 3 You'll need to a nd a way to quickly access a node's parent's right child and a node's parent's right sibling; this won't be trivial because the second one implies that the parent node's original right pointer has been overwritten. Hint 4 Recursively traverse the binary tree and sequence the transformation operations as follows: at any given node, recursively transform its left subtree into a right sibling tree, then edit the given node's right pointer to point to its right sibling, and then nally recursively transform its right subtree into a right sibling tree. This sequencing of operations will allow left child nodes to always access their parent's right child (before their parent's right pointer gets overwritten to point to the parent's right sibling) and will allow right child nodes to always access their parent's right sibling (after their parent's right pointer has gotten overwritten to point to the parent's right sibling). 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

```java 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 rightSiblingTree(BinaryTree root) { mutate(root, null, false); return root; } public static void mutate(BinaryTree node, BinaryTree parent, boolean isLeftChild) { if (node == null) return; var left = node.left; var right = node.right; mutate(left, node, true); if (parent == null) { node.right = null; } else if (isLeftChild) { node.right = parent.right; } else { if (parent.right == null) { node.right = null; } else { node.right = parent.right.left; } } mutate(right, node, false); } static class BinaryTree { int value; BinaryTree left = null; BinaryTree right = null; public BinaryTree(int value) { this.value = value; } } }

```

Test Cases

``` ▲

``` Test Case 1 { "tree": { "nodes": [ {"id": "1", "left": "2", "right": "3", "value": 1}, {"id": "3", "left": "6", "right": "7", "value": 3}, {"id": "7", "left": "12", "right": "13", "value": 7}, {"id": "13", "left": null, "right": null, "value": 13}, {"id": "12", "left": null, "right": null, "value": 12}, {"id": "6", "left": "11", "right": null, "value": 6}, {"id": "11", "left": "14", "right": null, "value": 11}, {"id": "14", "left": null, "right": null, "value": 14}, {"id": "2", "left": "4", "right": "5", "value": 2}, {"id": "5", "left": null, "right": "10", "value": 5}, {"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" } } 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": 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 9 { "tree": { "nodes": [ {"id": "1", "left": "2", "right": "3", "value": 1}, {"id": "3", "left": "6", "right": "7", "value": 3}, {"id": "7", "left": "14", "right": "15", "value": 7}, {"id": "15", "left": null, "right": null, "value": 15}, {"id": "14", "left": null, "right": null, "value": 14}, {"id": "6", "left": "12", "right": "13", "value": 6}, {"id": "13", "left": null, "right": null, "value": 13}, {"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" } }

``` Your submission failed at least one of our test cases.

```