Remove extra edge from a BST
Given a Binary Search Tree where an arbitrary node has 2 parents. Delete the extra edge and return the fixed Binary Search Tree.
Examples:
Input:
7
/ \
6 10
/ \ / \
2 9 11Output:
7
/ \
6 10
/ / \
2 9 11Explanation: The edge between 6 and 9 should be removed because it has 2 parents and it is a BST after removing it.
Input:
20
/ \
16 30
/ \
13 18Output:
20
/ \
16 30
/ \
13 18Explanation: No edge needed to be removed since it has not connected to multiple parents.
Approach: To solve the problem follow the below idea:
This problem can be solved using the logic of BST that when a node connected to two parents will violate the property of BST , so the edge which is causing the violation of property of BST that all the descendants to left should be less than the parent node and the descendants to right of parent node should be greater than parent node.
Follow these steps to solve this problem :
- Initialize the mini and maxi as INT_MIN and INT_MAX and pass it to the recursive function, In recursive function check
- If root is NULL return the NULL.
- If the current node does not satisfy the BST rule remove the edge by returning NULL to the parent
- Recursively move to left node and check the BST property return the root if the condition satisfies
- Recursively move to right node and check the BST property return the root if the condition satisfies
Here is the Implementation of the above approach :
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Tree node struct Node { int data; struct Node *left, *right; Node( int value) { data = value; left = right = NULL; } }; // Function to print the tree in inorder fashion void printInorder(Node* root) { if (root == NULL) return ; printInorder(root->left); cout << root->data << " "; printInorder(root->right); } // Function to remove the extre edge Node* removeExtraEdge(Node* root, int mini, int maxi) { // If root is NULL return the NULL. if (root == NULL) return NULL; // If the current node does not satisfy the // BST rule remove the edge by returning // NULL to the parent if (!(root->data < maxi and root->data > mini)) { return NULL; } // Recursively move to left node and check // the BST property return the root if the // condition satisfies root->left = removeExtraEdge(root->left, mini, root->data); // Recursively move to right node and check // the BST property return the root if the // condition satisfies root->right = removeExtraEdge(root->right, root->data, maxi); return root; } Node* removeExtraEdgeInBST(Node* root) { // Initialize the mini and maxi as // INT_MIN and INT_MAX return removeExtraEdge(root, INT_MIN, INT_MAX); } // Driver code int main() { // 7 // / \ // 6 10 // / \ / \ // 2 9 11 struct Node* root = new Node(7); root->left = new Node(6); root->right = new Node(10); root->left->left = new Node(2); root->left->right = new Node(9); root->right->left = new Node(9); root->right->right = new Node(11); // Print the nodes in inorder traversal // before removing they appear unsorted cout << "Inoder traversal before edge removal : "; printInorder(root); cout << endl; Node* afterChange = removeExtraEdgeInBST(root); cout << "Inoder traversal after edge removal : "; // Print the nodes in inorder traversal // before removing they appear sorted printInorder(afterChange); return 0; } |
Java
class Node { int data; Node left, right; public Node( int value) { data = value; left = right = null ; } } public class BinaryTree { // Function to print the tree in inorder fashion static void printInorder(Node root) { if (root == null ) return ; printInorder(root.left); System.out.print(root.data + " " ); printInorder(root.right); } // Function to remove the extra edge static Node removeExtraEdge(Node root, int mini, int maxi) { // If root is NULL, return NULL. if (root == null ) return null ; // If the current node does not satisfy the // BST rule, remove the edge by returning // NULL to the parent if (!(root.data < maxi && root.data > mini)) { return null ; } // Recursively move to the left node and check // the BST property, return the root if the // condition satisfies root.left = removeExtraEdge(root.left, mini, root.data); // Recursively move to the right node and check // the BST property, return the root if the // condition satisfies root.right = removeExtraEdge(root.right, root.data, maxi); return root; } // Function to remove the extra edge in the BST static Node removeExtraEdgeInBST(Node root) { // Initialize the mini and maxi as // Integer.MIN_VALUE and Integer.MAX_VALUE return removeExtraEdge(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } // Driver code public static void main(String[] args) { // Build the binary search tree Node root = new Node( 7 ); root.left = new Node( 6 ); root.right = new Node( 10 ); root.left.left = new Node( 2 ); root.left.right = new Node( 9 ); root.right.left = new Node( 9 ); root.right.right = new Node( 11 ); // Print the nodes in inorder traversal // before removing; they appear unsorted System.out.print( "Inorder traversal before edge removal: " ); printInorder(root); System.out.println(); // Remove extra edges violating BST property Node afterChange = removeExtraEdgeInBST(root); System.out.print( "Inorder traversal after edge removal: " ); // Print the nodes in inorder traversal // after removing; they appear sorted printInorder(afterChange); } } |
Python3
# Python code for the above approach # Tree node class Node: def __init__( self , value): self .data = value self .left = self .right = None # Function to print the tree in inorder fashion def printInorder(root): if root is None : return printInorder(root.left) print (root.data, end = " " ) printInorder(root.right) # Function to remove the extra edge def removeExtraEdge(root, mini, maxi): # If root is None, return None if root is None : return None # If the current node does not satisfy the # BST rule, remove the edge by returning # None to the parent if not (mini < root.data < maxi): return None # Recursively move to the left node and check # the BST property; return the root if the # condition satisfies root.left = removeExtraEdge(root.left, mini, root.data) # Recursively move to the right node and check # the BST property; return the root if the # condition satisfies root.right = removeExtraEdge(root.right, root.data, maxi) return root # Function to remove the extra edge in BST def removeExtraEdgeInBST(root): # Initialize mini and maxi as # negative and positive infinity return removeExtraEdge(root, float ( '-inf' ), float ( 'inf' )) # Driver code if __name__ = = "__main__" : # 7 # / \ # 6 10 # / \ / \ # 2 9 11 root = Node( 7 ) root.left = Node( 6 ) root.right = Node( 10 ) root.left.left = Node( 2 ) root.left.right = Node( 9 ) root.right.left = Node( 9 ) root.right.right = Node( 11 ) # Print the nodes in inorder traversal # before removing; they appear unsorted print ( "Inorder traversal before edge removal:" , end = " " ) printInorder(root) print () after_change = removeExtraEdgeInBST(root) print ( "Inorder traversal after edge removal:" , end = " " ) # Print the nodes in inorder traversal # after removing; they appear sorted printInorder(after_change) |
C#
// C# Implementation using System; public class Node { public int data; public Node left, right; public Node( int value) { data = value; left = right = null ; } } public class BinaryTree { // Function to print the tree in inorder fashion static void PrintInorder(Node root) { if (root == null ) return ; PrintInorder(root.left); Console.Write(root.data + " " ); PrintInorder(root.right); } // Function to remove the extra edge static Node RemoveExtraEdge(Node root, int mini, int maxi) { // If root is NULL, return NULL. if (root == null ) return null ; // If the current node does not satisfy the // BST rule, remove the edge by returning // NULL to the parent if (!(root.data < maxi && root.data > mini)) { return null ; } // Recursively move to the left node and check // the BST property, return the root if the // condition satisfies root.left = RemoveExtraEdge(root.left, mini, root.data); // Recursively move to the right node and check // the BST property, return the root if the // condition satisfies root.right = RemoveExtraEdge(root.right, root.data, maxi); return root; } // Function to remove the extra edge in the BST static Node RemoveExtraEdgeInBST(Node root) { // Initialize the mini and maxi as // Int32.MinValue and Int32.MaxValue return RemoveExtraEdge(root, Int32.MinValue, Int32.MaxValue); } // Driver code public static void Main( string [] args) { // Build the binary search tree Node root = new Node(7); root.left = new Node(6); root.right = new Node(10); root.left.left = new Node(2); root.left.right = new Node(9); root.right.left = new Node(9); root.right.right = new Node(11); // Print the nodes in inorder traversal // before removing; they appear unsorted Console.Write( "Inorder traversal before edge removal: " ); PrintInorder(root); Console.WriteLine(); // Remove extra edges violating BST property Node afterChange = RemoveExtraEdgeInBST(root); Console.Write( "Inorder traversal after edge removal: " ); // Print the nodes in inorder traversal // after removing; they appear sorted PrintInorder(afterChange); } } // Thsi code is contributed by Sakshi |
Javascript
// JavaScript code for the above approach // Tree node class Node { constructor(value) { this .data = value; this .left = null ; this .right = null ; } } // Function to print the tree in inorder fashion function printInorder(root) { if (root === null ) return ; printInorder(root.left); console.log(root.data + " " ); printInorder(root.right); } // Function to remove the extra edge function removeExtraEdge(root, mini, maxi) { // If root is NULL return the NULL. if (root === null ) return null ; // If the current node does not satisfy the // BST rule remove the edge by returning // NULL to the parent if (!(root.data < maxi && root.data > mini)) { return null ; } // Recursively move to left node and check // the BST property return the root if the // condition satisfies root.left = removeExtraEdge(root.left, mini, root.data); // Recursively move to right node and check // the BST property return the root if the // condition satisfies root.right = removeExtraEdge(root.right, root.data, maxi); return root; } function removeExtraEdgeInBST(root) { return removeExtraEdge(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER); } // Driver code function main() { // 7 // / \ // 6 10 // / \ / \ // 2 9 9 11 let root = new Node(7); root.left = new Node(6); root.right = new Node(10); root.left.left = new Node(2); root.left.right = new Node(9); root.right.left = new Node(9); root.right.right = new Node(11); // Print the nodes in inorder traversal // before removing they appear unsorted console.log( "Inorder traversal before edge removal: " ); printInorder(root); console.log(); let afterChange = removeExtraEdgeInBST(root); console.log( "Inorder traversal after edge removal: " ); // Print the nodes in inorder traversal // after removing they appear sorted printInorder(afterChange); } // Run the main function main(); |
Inoder traversal before edge removal : 2 6 9 7 9 10 11 Inoder traversal after edge removal : 2 6 7 9 10 11
Time Complexity: O(N),N is the number of nodes in the tree.
Auxiliary space: O(h),h is the height of tree.
Contact Us