Correct a Binary Tree
TCSThe problem
Given the root of a binary tree with n nodes, each node contains a unique integer value. However, exactly one node has an incorrect right child that points to another node at the same level instead of nullptr. The task is to correct the tree by removing the incorrectly assigned right child and return the corrected tree.
The test input is read as 3 lines:
- TreeNode root
- int fromNode (not passed to correctBinaryTree)
- int toNode (not passed to correctBinaryTree)
After the binary tree rooted at root is parsed, the TreeNode with value of fromNode will have its right child pointer pointing to the TreeNode with a value of toNode. Then, root is passed to correctBinaryTree.
Input: root = [1,2,3], fromNode = 2, toNode = 3 Output: [1,null,3] Explanation: The node with value 2 is invalid, so remove it.
Input: root = [8,3,1,7,null,9,4,2,null,null,null,5,6], fromNode = 7, toNode = 4 Output: [8,3,1,null,null,9,4,null,null,5,6] Explanation: The node with value 7 is invalid, so remove it and the node underneath it, node 2.
Input: root = [10,5,15,3,7,null,18,1,4,null,null,6,null,null,null], fromNode = 7, toNode = 18
- The number of nodes in the tree is in the range [3, 104].
- -109 <= Node.val <= 109
- All Node.val are unique.
- fromNode != toNode
- fromNode and toNode will exist in the tree and will be on the same depth.
- toNode is to the right of fromNode.
- fromNode.right is null in the initial tree from the test data.
cpp
/**
* Definition for a binary tree node.
* class TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* correctBinaryTree(TreeNode* root) {
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode correctBinaryTree(TreeNode root) {
// Your Code Goes Here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.data = x
# self.left = None
# self.right = None
class Solution:
def correctBinaryTree(self, root):javascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
correctBinaryTree(root) {
//your code goes here
}
}csharp
/*
public class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
data = val;
left = null;
right = null;
}
}
*/
class Solution {
public TreeNode CorrectBinaryTree(TreeNode root) {
//your code goes here
}
}go
/*
type TreeNode struct {
Data int
Left *TreeNode
Right *TreeNode
}
*/
func correctBinaryTree(root *TreeNode) *TreeNode {
}Stuck? Show a way to structure it+
- 01Traverse level by level from right to left.
- 02Keep a set of nodes already seen on that level, which are to the right.
- 03If a node's right child is already seen, that node is invalid.
- 04Do not attach the invalid node to the next level; enqueue only valid children.
Reference answer
Then expect these follow-ups
Why does the problem guarantee the target is to the right of the invalid node?
Tests: proof of invariant
How would you return the parent and side of the invalid node instead?
Tests: tree bookkeeping
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question