Maximum absolute difference between the sibling nodes of given BST
Given a BST (Binary Search Tree) with N Nodes, the task is to find the maximum absolute difference between the sibling nodes.
Two nodes are said to be siblings if they are present at the same level, and their parents are the same.]
Examples:
Input:
Output: 70
Explanation:
105 β 50 = 55 (As 105 and 50 nodes are siblings)
75 β 5 = 70 (As 75 and 5 nodes are siblings)
106 β 101 = 5 (As 106 and 5 nodes are siblings)
Other than these, there is no other pair of nodes that are siblings.
So among them the max difference is 70. (75 β 5 = 70)Input:
Output: 60
Explanation:
120 β 60 = 60
90 β 45 = 45
160 β 110 = 50
Other than these, there is no other pair of nodes that are siblings.
So among them the max difference is 60. (120 β 60 = 60)
Approach:
The basic Idea is to check whether the nodes are siblings or not if sibling then find out the maximum difference.
Follow the steps mentioned below to implement the idea:
- Iterate the BST in the preorder fashion. Root Left Right.
- At every point,
- Check if the left and right children are available.
- If both are available, then calculate the difference between the right and left values. (By default BST right val > left val)
- Maximize the absolute maximum difference.
- Else just continue the traversal.
- After the traversal ends, return the maximum difference between the sibling nodes.
Below is the Implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Structure of a BST node struct TreeNode { int val; struct TreeNode *left, *right; }; // Function to form a new node TreeNode* newNode( int data) { TreeNode* temp = new TreeNode; temp->val = data; temp->left = NULL; temp->right = NULL; return temp; } // Function to insert a new node to the BST TreeNode* insert(TreeNode* root, int val) { TreeNode* newnode = newNode(val); TreeNode* x = root; TreeNode* y = NULL; while (x != NULL) { y = x; if (val < x->val) x = x->left; else x = x->right; } if (y == NULL) y = newnode; else if (val < y->val) y->left = newnode; else y->right = newnode; return y; } // Function to find the maximum absolute difference void findMaxDiff(TreeNode* root, int & max_diff) { if (root == NULL) { return ; } int lval, rval; // Only when both siblings are there if (root->left != NULL && root->right != NULL) { lval = root->left->val; rval = root->right->val; max_diff = max(max_diff, rval - lval); } findMaxDiff(root->left, max_diff); findMaxDiff(root->right, max_diff); } // Driver code int main() { TreeNode* root = NULL; TreeNode* root2 = NULL; // Structure of first tree root = insert(root, 100); insert(root, 50); insert(root, 105); insert(root, 75); insert(root, 5); insert(root, 101); insert(root, 106); // Structure of second tree root2 = insert(root2, 100); insert(root2, 60); insert(root2, 120); insert(root2, 45); insert(root2, 90); insert(root2, 110); insert(root2, 160); int max_diff = INT_MIN; int max_diff2 = INT_MIN; findMaxDiff(root, max_diff); cout << max_diff << "\n" ; findMaxDiff(root2, max_diff2); cout << max_diff2 << "\n" ; return 0; } |
Java
// java code implementation import java.util.Scanner; class TreeNode { int val; TreeNode left, right; TreeNode( int val) { this .val = val; this .left = null ; this .right = null ; } } class GFG { // Function to form a new node public static TreeNode newNode( int data) { TreeNode temp = new TreeNode(data); return temp; } // Function to insert a new node to the BST public static TreeNode insert(TreeNode root, int val) { TreeNode newnode = newNode(val); TreeNode x = root; TreeNode y = null ; while (x != null ) { y = x; if (val < x.val) x = x.left; else x = x.right; } if (y == null ) y = newnode; else if (val < y.val) y.left = newnode; else y.right = newnode; return y; } // Function to find the maximum absolute difference public static void findMaxDiff(TreeNode root, int [] max_diff) { if (root == null ) { return ; } int lval, rval; // Only when both siblings are there if (root.left != null && root.right != null ) { lval = root.left.val; rval = root.right.val; max_diff[ 0 ] = Math.max(max_diff[ 0 ], rval - lval); } findMaxDiff(root.left, max_diff); findMaxDiff(root.right, max_diff); } // Driver code public static void main(String[] args) { TreeNode root = null ; TreeNode root2 = null ; // Structure of first tree root = insert(root, 100 ); insert(root, 50 ); insert(root, 105 ); insert(root, 75 ); insert(root, 5 ); insert(root, 101 ); insert(root, 106 ); // Structure of second tree root2 = insert(root2, 100 ); insert(root2, 60 ); insert(root2, 120 ); insert(root2, 45 ); insert(root2, 90 ); insert(root2, 110 ); insert(root2, 160 ); int [] max_diff = { Integer.MIN_VALUE }; int [] max_diff2 = { Integer.MIN_VALUE }; findMaxDiff(root, max_diff); System.out.println(max_diff[ 0 ]); findMaxDiff(root2, max_diff2); System.out.println(max_diff2[ 0 ]); } } // This code is contributed by ksam24000 |
Python3
# Python code implementation class TreeNode: def __init__( self , val): self .val = val self .left = None self .right = None # Function to form a new node def newNode(data): temp = TreeNode(data) return temp # Function to insert a new node to the BST def insert(root, val): newnode = newNode(val) x = root y = None while x is not None : y = x if val < x.val: x = x.left else : x = x.right if y is None : y = newnode elif val < y.val: y.left = newnode else : y.right = newnode return y # Function to find the maximum absolute difference def findMaxDiff(root, max_diff): if root is None : return lval, rval = None , None # Only when both siblings are there if root.left is not None and root.right is not None : lval = root.left.val rval = root.right.val max_diff[ 0 ] = max (max_diff[ 0 ], rval - lval) findMaxDiff(root.left, max_diff) findMaxDiff(root.right, max_diff) root = None root2 = None # Structure of first tree root = insert(root, 100 ) insert(root, 50 ) insert(root, 105 ) insert(root, 75 ) insert(root, 5 ) insert(root, 101 ) insert(root, 106 ) # Structure of second tree root2 = insert(root2, 100 ) insert(root2, 60 ) insert(root2, 120 ) insert(root2, 45 ) insert(root2, 90 ) insert(root2, 110 ) insert(root2, 160 ) max_diff = [ float ( "-inf" )] max_diff2 = [ float ( "-inf" )] findMaxDiff(root, max_diff) print (max_diff[ 0 ]) findMaxDiff(root2, max_diff2) print (max_diff2[ 0 ]) # This code is contributed by lokesh. |
C#
// C# code implementation using System; class TreeNode { public int val; public TreeNode left, right; public TreeNode( int val) { this .val = val; this .left = null ; this .right = null ; } } public class GFG { // Function to form a new node static TreeNode newNode( int data) { TreeNode temp = new TreeNode(data); return temp; } // Function to insert a new node to the BST static TreeNode insert(TreeNode root, int val) { TreeNode newnode = newNode(val); TreeNode x = root; TreeNode y = null ; while (x != null ) { y = x; if (val < x.val) x = x.left; else x = x.right; } if (y == null ) y = newnode; else if (val < y.val) y.left = newnode; else y.right = newnode; return y; } // Function to find the maximum absolute difference static void findMaxDiff(TreeNode root, int [] max_diff) { if (root == null ) { return ; } int lval, rval; // Only when both siblings are there if (root.left != null && root.right != null ) { lval = root.left.val; rval = root.right.val; max_diff[0] = Math.Max(max_diff[0], rval - lval); } findMaxDiff(root.left, max_diff); findMaxDiff(root.right, max_diff); } static public void Main() { // Code TreeNode root = null ; TreeNode root2 = null ; // Structure of first tree root = insert(root, 100); insert(root, 50); insert(root, 105); insert(root, 75); insert(root, 5); insert(root, 101); insert(root, 106); // Structure of second tree root2 = insert(root2, 100); insert(root2, 60); insert(root2, 120); insert(root2, 45); insert(root2, 90); insert(root2, 110); insert(root2, 160); int [] max_diff = { Int32.MinValue }; int [] max_diff2 = { Int32.MinValue }; findMaxDiff(root, max_diff); Console.WriteLine(max_diff[0]); findMaxDiff(root2, max_diff2); Console.WriteLine(max_diff2[0]); } } // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript Code to implement the approach // Structure of a BST node class TreeNode{ constructor(data){ this .val = data; this .left = null ; this .right = null ; } } // Function to insert a new node to the BST function insert(root, val){ let newnode = new TreeNode(val); let x = root; let y = null ; while (x != null ){ y = x; if (val < x.val) x = x.left; else x = x.right; } if (y == null ){ y = newnode; } else if (val < y.val){ y.left = newnode; } else { y.right = newnode; } return y; } // Function to find the maximum absolute difference function findMaxDiff(root, max_diff){ if (root == null ) return ; let lval, rval; // Only when both siblings are there if (root.left != null && root.right != null ){ lval = root.left.val; rval = root.right.val; max_diff[0] = Math.max(max_diff[0], rval-lval); } findMaxDiff(root.left, max_diff); findMaxDiff(root.right, max_diff); } // Driver Code let root = null ; let root2 = null ; // structure of first tree root = insert(root, 100); insert(root, 50); insert(root, 105); insert(root, 75); insert(root, 5); insert(root, 101); insert(root, 106); // Structure of second tree root2 = insert(root2, 100); insert(root2, 60); insert(root2, 120); insert(root2, 45); insert(root2, 90); insert(root2, 110); insert(root2, 160); let max_diff = [Number.MIN_VALUE]; let max_diff2 = [Number.MIN_VALUE]; findMaxDiff(root, max_diff); document.write(max_diff[0]); document.write( "<br>" ); findMaxDiff(root2, max_diff2); document.write(max_diff2[0]); // This code is contributed by Yash Agarwal |
70 60
Time Complexity: O(N)
Auxiliary Space: O(h)
Related Articles:
- Introduction to Binary Search Tree β Data Structure and Algorithm Tutorials
- Insertion in Binary Search Tree