Maksimālais elements starp diviem BST mezgliem
Ņemot vērā masīvu n elementi un divi veseli skaitļi a b kas pieder dotajam masīvam. Izveidot a Binārais meklēšanas koks ievietojot elementus no arr[0] uz arr[n-1] . Uzdevums ir atrast maksimums elements ceļā no a līdz b.
Piemērs:
Ievade: arr[] = { 18 36 9 6 12 10 1 8 } a = 1 b = 10.
Izvade: 12
Paskaidrojums: Ceļš no 1 līdz 10 satur { 1 6 9 12 10 } . Maksimālais elements ir 12.
Satura rādītājs
- [Naiva pieeja] Izmantojot jaukšanu - O(n * log n) laiks un O(n) telpa
- [Paredzamā pieeja] Izmantojot divu mezglu LCA - O(h) laiks un O(h) telpa
[Naiva pieeja] Izmantojot jaukšanu - O(n * log n) laiks un O(n) telpa
Ideja ir izmantot a hashmap uzglabāt vecāks katra mezgla mezgls binārā meklēšanas koks . Mēs varam sākt no abiem dotajiem mezgliem un šķērsot koku, kurā tiek glabāti mezgli, kas sastopami a komplekts . Kad esam sasnieguši abu mezglu sakni vai kopīgo priekšteci, mēs varam šķērsot koku no katra mezgla un atrast maksimums mezglu kopā atrastais elements.
Iepriekš minētās pieejas algoritma darbības:
- Izveidojiet tukšu hash tabula uzglabāt vecāks katra mezgla mezgls binārajā meklēšanas kokā.
- Veiciet a dziļuma pirmā meklēšana (DFS) binārā meklēšanas koka šķērsošana un aizpildiet hash tabulu ar katra mezgla vecāku mezglu.
- Inicializējiet divus rādītājus p1 un p2 uz dotajiem mezgliem.
- Inicializējiet divas tukšas kopas s1 un s2 lai saglabātu mezglus, kas radušies, šķērsojot koku augšup no p1 un p2 attiecīgi.
- Kamēr p1 un p2 ir nav vienāds rīkojieties šādi:
- Ja p1 nav null pievienojiet to kopai s1 un atjaunināt p1 uz vecāku mezglu, izmantojot jaucējtabulu.
- Ja p2 nav null pievienojiet to kopai s2 un atjaunināt p2 uz vecāku mezglu, izmantojot jaucējtabulu.
- Atrodiet krustojumu kopu s1 un s2 t.i., mezglu kopa, kas ir kopīga gan s1, gan s2.
- Šajā krustojumā atrast maksimums elementu un atgrieziet to.
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
C++ // C++ program to find maximum element in the path // between two Nodes of Binary Search Tree. #include using namespace std ; class Node { public : int data ; Node * left * right ; Node ( int x ) { data = x ; left = right = nullptr ; } }; // Insert a new Node in Binary Search Tree void insertNode ( Node *& root int x ) { Node * current = root * parent = nullptr ; // Traverse to the correct position for insertion while ( current != nullptr ) { parent = current ; if ( x < current -> data ) current = current -> left ; else current = current -> right ; } // Insert new Node at the correct position if ( parent == nullptr ) root = new Node ( x ); else if ( x < parent -> data ) parent -> left = new Node ( x ); else parent -> right = new Node ( x ); } // DFS to populate parent map for each node void dfs ( Node * root unordered_map < Node * Node *> & parentMap Node * parent = nullptr ) { if ( ! root ) return ; // Store the parent of the current node if ( parent != nullptr ) { parentMap [ root ] = parent ; } // Recur for left and right children dfs ( root -> left parentMap root ); dfs ( root -> right parentMap root ); } // Function to find the node with the given value in the BST Node * findNode ( Node * root int val ) { if ( ! root ) return nullptr ; if ( root -> data == val ) return root ; Node * leftResult = findNode ( root -> left val ); if ( leftResult ) return leftResult ; return findNode ( root -> right val ); } // Find maximum element in the path between two nodes in BST int findMaxElement ( Node * root int x int y ) { unordered_map < Node * Node *> parentMap ; // Populate parent map with DFS dfs ( root parentMap ); // Find the nodes corresponding to the // values x and y Node * p1 = findNode ( root x ); Node * p2 = findNode ( root y ); // If nodes not found if ( ! p1 || ! p2 ) return -1 ; // Sets to store nodes encountered // while traversing up the tree unordered_set < Node *> s1 s2 ; // Variable to store the maximum // element in the path int maxElement = INT_MIN ; // Traverse up the tree from p1 and p2 // and add nodes to sets s1 and s2 while ( p1 != p2 ) { if ( p1 ) { s1 . insert ( p1 ); maxElement = max ( maxElement p1 -> data ); // Move to parent node p1 = parentMap [ p1 ]; } if ( p2 ) { s2 . insert ( p2 ); maxElement = max ( maxElement p2 -> data ); p2 = parentMap [ p2 ]; } // Check if there's a common node // in both sets if ( s1 . count ( p2 )) break ; if ( s2 . count ( p1 )) break ; } // Now both p1 and p2 point to their Lowest // Common Ancestor (LCA) maxElement = max ( maxElement p1 -> data ); return maxElement ; } int main () { vector < int > arr = { 18 36 9 6 12 10 1 8 }; int a = 1 b = 10 ; int n = arr . size (); Node * root = new Node ( arr [ 0 ]); for ( int i = 1 ; i < n ; i ++ ) insertNode ( root arr [ i ]); cout < < findMaxElement ( root a b ) < < endl ; return 0 ; }
Java // Java program to find the maximum element in the path // between two Nodes of Binary Search Tree. import java.util.* ; class Node { int data ; Node left right ; Node ( int x ) { data = x ; left = right = null ; } } class GfG { // Insert a new Node in Binary Search Tree static void insertNode ( Node root int x ) { Node current = root parent = null ; // Traverse to the correct position // for insertion while ( current != null ) { parent = current ; if ( x < current . data ) current = current . left ; else current = current . right ; } // Insert new Node at the correct position if ( parent == null ) root = new Node ( x ); else if ( x < parent . data ) parent . left = new Node ( x ); else parent . right = new Node ( x ); } // DFS to populate parent map for each node static void dfs ( Node root Map < Node Node > parentMap Node parent ) { if ( root == null ) return ; // Store the parent of the current node if ( parent != null ) { parentMap . put ( root parent ); } // Recur for left and right children dfs ( root . left parentMap root ); dfs ( root . right parentMap root ); } // Function to find the node with the given // value in the BST static Node findNode ( Node root int val ) { if ( root == null ) return null ; if ( root . data == val ) return root ; Node leftResult = findNode ( root . left val ); if ( leftResult != null ) return leftResult ; return findNode ( root . right val ); } // Find maximum element in the path between // two nodes in BST static int findMaxElement ( Node root int x int y ) { Map < Node Node > parentMap = new HashMap <> (); // Populate parent map with DFS dfs ( root parentMap null ); // Find the nodes corresponding to // the values x and y Node p1 = findNode ( root x ); Node p2 = findNode ( root y ); // If nodes not found if ( p1 == null || p2 == null ) return - 1 ; // Sets to store nodes encountered // while traversing up the tree Set < Node > s1 = new HashSet <> (); Set < Node > s2 = new HashSet <> (); // Variable to store the maximum element // in the path int maxElement = Integer . MIN_VALUE ; // Traverse up the tree from p1 and p2 // and add nodes to sets s1 and s2 while ( p1 != p2 ) { if ( p1 != null ) { s1 . add ( p1 ); maxElement = Math . max ( maxElement p1 . data ); // Move to parent node p1 = parentMap . get ( p1 ); } if ( p2 != null ) { s2 . add ( p2 ); maxElement = Math . max ( maxElement p2 . data ); p2 = parentMap . get ( p2 ); } // Check if there's a common node in both sets if ( s1 . contains ( p2 )) break ; if ( s2 . contains ( p1 )) break ; } // Now both p1 and p2 point to their // Lowest Common Ancestor (LCA) maxElement = Math . max ( maxElement p1 . data ); return maxElement ; } public static void main ( String [] args ) { int [] arr = { 18 36 9 6 12 10 1 8 }; int a = 1 b = 10 ; int n = arr . length ; Node root = new Node ( arr [ 0 ] ); for ( int i = 1 ; i < n ; i ++ ) insertNode ( root arr [ i ] ); System . out . println ( findMaxElement ( root a b )); } }
Python # Python program to find maximum element in the path # between two Nodes of Binary Search Tree. class Node : def __init__ ( self x ): self . data = x self . left = None self . right = None # Insert a new Node in Binary Search Tree def insert_node ( root x ): current = root parent = None # Traverse to the correct position for insertion while current is not None : parent = current if x < current . data : current = current . left else : current = current . right # Insert new Node at the correct position if parent is None : root = Node ( x ) elif x < parent . data : parent . left = Node ( x ) else : parent . right = Node ( x ) # DFS to populate parent map for each node def dfs ( root parent_map parent = None ): if root is None : return # Store the parent of the current node if parent is not None : parent_map [ root ] = parent # Recur for left and right children dfs ( root . left parent_map root ) dfs ( root . right parent_map root ) # Function to find the node with the given # value in the BST def find_node ( root val ): if root is None : return None if root . data == val : return root left_result = find_node ( root . left val ) if left_result : return left_result return find_node ( root . right val ) # Find maximum element in the path between # two nodes in BST def find_max_element ( root x y ): parent_map = {} # Populate parent map with DFS dfs ( root parent_map ) # Find the nodes corresponding to the # values x and y p1 = find_node ( root x ) p2 = find_node ( root y ) # If nodes not found if not p1 or not p2 : return - 1 # Sets to store nodes encountered # while traversing up the tree s1 = set () s2 = set () # Variable to store the maximum element in the path max_element = float ( '-inf' ) # Traverse up the tree from p1 and p2 # and add nodes to sets s1 and s2 while p1 != p2 : if p1 : s1 . add ( p1 ) max_element = max ( max_element p1 . data ) # Move to parent node p1 = parent_map . get ( p1 ) if p2 : s2 . add ( p2 ) max_element = max ( max_element p2 . data ) p2 = parent_map . get ( p2 ) # Check if there's a common node in both sets if p2 in s1 : break if p1 in s2 : break # Now both p1 and p2 point to their # Lowest Common Ancestor (LCA) max_element = max ( max_element p1 . data ) return max_element if __name__ == '__main__' : arr = [ 18 36 9 6 12 10 1 8 ] a b = 1 10 n = len ( arr ) root = Node ( arr [ 0 ]) for i in range ( 1 n ): insert_node ( root arr [ i ]) print ( find_max_element ( root a b ))
C# // C# program to find the maximum element in the path // between two Nodes of Binary Search Tree. using System ; using System.Collections.Generic ; class Node { public int data ; public Node left right ; public Node ( int x ) { data = x ; left = right = null ; } } class GfG { // Insert a new Node in Binary Search Tree static public void insertNode ( Node root int x ) { Node current = root parent = null ; // Traverse to the correct position // for insertion while ( current != null ) { parent = current ; if ( x < current . data ) current = current . left ; else current = current . right ; } // Insert new Node at the correct // position if ( parent == null ) root = new Node ( x ); else if ( x < parent . data ) parent . left = new Node ( x ); else parent . right = new Node ( x ); } // DFS to populate parent map for each node static public void dfs ( Node root Dictionary < Node Node > parentMap Node parent ) { if ( root == null ) return ; // Store the parent of the current node if ( parent != null ) { parentMap [ root ] = parent ; } // Recur for left and right children dfs ( root . left parentMap root ); dfs ( root . right parentMap root ); } // Function to find the node with the given // value in the BST static public Node findNode ( Node root int val ) { if ( root == null ) return null ; if ( root . data == val ) return root ; Node leftResult = findNode ( root . left val ); if ( leftResult != null ) return leftResult ; return findNode ( root . right val ); } // Find maximum element in the path between // two nodes in BST static public int findMaxElement ( Node root int x int y ) { Dictionary < Node Node > parentMap = new Dictionary < Node Node > (); // Populate parent map with DFS dfs ( root parentMap null ); // Find the nodes corresponding to // the values x and y Node p1 = findNode ( root x ); Node p2 = findNode ( root y ); // If nodes not found if ( p1 == null || p2 == null ) return - 1 ; // Sets to store nodes encountered // while traversing up the tree HashSet < Node > s1 = new HashSet < Node > (); HashSet < Node > s2 = new HashSet < Node > (); // Variable to store the maximum element // in the path int maxElement = int . MinValue ; // Traverse up the tree from p1 and p2 // and add nodes to sets s1 and s2 while ( p1 != p2 ) { if ( p1 != null ) { s1 . Add ( p1 ); maxElement = Math . Max ( maxElement p1 . data ); // Move to parent node p1 = parentMap [ p1 ]; } if ( p2 != null ) { s2 . Add ( p2 ); maxElement = Math . Max ( maxElement p2 . data ); p2 = parentMap [ p2 ]; } // Check if there's a common node in both sets if ( s1 . Contains ( p2 )) break ; if ( s2 . Contains ( p1 )) break ; } // Now both p1 and p2 point to their Lowest // Common Ancestor (LCA) maxElement = Math . Max ( maxElement p1 . data ); return maxElement ; } static void Main () { int [] arr = { 18 36 9 6 12 10 1 8 }; int a = 1 b = 10 ; int n = arr . Length ; Node root = new Node ( arr [ 0 ]); for ( int i = 1 ; i < n ; i ++ ) insertNode ( root arr [ i ]); Console . WriteLine ( findMaxElement ( root a b )); } }
JavaScript // JavaScript program to find the maximum element in the path // between two Nodes of Binary Search Tree. class Node { constructor ( x ) { this . data = x ; this . left = this . right = null ; } } // Insert a new Node in Binary Search Tree function insertNode ( root x ) { let current = root parent = null ; // Traverse to the correct position for insertion while ( current !== null ) { parent = current ; if ( x < current . data ) current = current . left ; else current = current . right ; } // Insert new Node at the correct position if ( parent === null ) root = new Node ( x ); else if ( x < parent . data ) parent . left = new Node ( x ); else parent . right = new Node ( x ); } // DFS to populate parent map for each node function dfs ( root parentMap parent = null ) { if ( root === null ) return ; // Store the parent of the current node if ( parent !== null ) { parentMap . set ( root parent ); } // Recur for left and right children dfs ( root . left parentMap root ); dfs ( root . right parentMap root ); } // Function to find the node with the given // value in the BST function findNode ( root val ) { if ( root === null ) return null ; if ( root . data === val ) return root ; let leftResult = findNode ( root . left val ); if ( leftResult !== null ) return leftResult ; return findNode ( root . right val ); } // Find maximum element in the path // between two nodes in BST function findMaxElement ( root x y ) { let parentMap = new Map (); // Populate parent map with DFS dfs ( root parentMap ); // Find the nodes corresponding to the // values x and y let p1 = findNode ( root x ); let p2 = findNode ( root y ); // If nodes not found if ( p1 === null || p2 === null ) return - 1 ; // Sets to store nodes encountered let s1 = new Set (); let s2 = new Set (); // Variable to store the maximum // element in the path let maxElement = - Infinity ; // Traverse up the tree from p1 and p2 // and add nodes to sets s1 and s2 while ( p1 !== p2 ) { if ( p1 !== null ) { s1 . add ( p1 ); maxElement = Math . max ( maxElement p1 . data ); // Move to parent node p1 = parentMap . get ( p1 ); } if ( p2 !== null ) { s2 . add ( p2 ); maxElement = Math . max ( maxElement p2 . data ); p2 = parentMap . get ( p2 ); } // Check if there's a common node in both sets if ( s1 . has ( p2 )) break ; if ( s2 . has ( p1 )) break ; } // Now both p1 and p2 point to their Lowest // Common Ancestor (LCA) maxElement = Math . max ( maxElement p1 . data ); return maxElement ; } let arr = [ 18 36 9 6 12 10 1 8 ]; let a = 1 b = 10 ; let n = arr . length ; let root = new Node ( arr [ 0 ]); for ( let i = 1 ; i < n ; i ++ ) insertNode ( root arr [ i ]); console . log ( findMaxElement ( root a b ));
Izvade
12
[Paredzamā pieeja] Izmantojot divu mezglu LCA - O(h) laiks un O(h) telpa
Ideja ir atrast Zemākais kopējais sencis no mezgla “a” un mezgla “b”. Pēc tam meklējiet maksimālo mezglu starp LCA un “a”, kā arī atrodiet maksimālo mezglu starp LCA un “b”. Atbilde būs maksimālais mezgls ar diviem.
Zemāk ir aprakstīta iepriekš minētā algoritma ieviešana:
C++ // C++ program to find maximum element in the path // between two Nodes of Binary Search Tree. #include using namespace std ; class Node { public : Node * left * right ; int data ; Node ( int x ) { data = x ; left = right = nullptr ; } }; // Insert a new Node in Binary Search Tree. void insertNode ( struct Node * root int x ) { Node * current = root * parent = nullptr ; while ( current != nullptr ) { parent = current ; if ( current -> data < x ) current = current -> right ; else current = current -> left ; } if ( parent == nullptr ) current = new Node ( x ); else { if ( parent -> data < x ) parent -> right = new Node ( x ); else parent -> left = new Node ( x ); } } // Return the maximum element between a Node // and its given ancestor. int maxelpath ( Node * root int x ) { Node * current = root ; int mx = INT_MIN ; // Traversing the path between ancestor and // Node and finding maximum element. while ( current -> data != x ) { if ( current -> data > x ) { mx = max ( mx current -> data ); current = current -> left ; } else { mx = max ( mx current -> data ); current = current -> right ; } } return max ( mx x ); } // Return maximum element in the path between // two given Node of BST. int maximumElement ( Node * root int x int y ) { Node * current = root ; // Finding the LCA of Node x and Node y while (( x < current -> data && y < current -> data ) || ( x > current -> data && y > current -> data )) { // Checking if both the Node lie on the // left side of the parent p. if ( x < current -> data && y < current -> data ) current = current -> left ; // Checking if both the Node lie on the // right side of the parent p. else if ( x > current -> data && y > current -> data ) current = current -> right ; } // Return the maximum of maximum elements occur // in path from ancestor to both Node. return max ( maxelpath ( current x ) maxelpath ( current y )); } int main () { int arr [] = { 18 36 9 6 12 10 1 8 }; int a = 1 b = 10 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); Node * root = new Node ( arr [ 0 ]); for ( int i = 1 ; i < n ; i ++ ) insertNode ( root arr [ i ]); cout < < maximumElement ( root a b ) < < endl ; return 0 ; }
Java // Java program to find maximum element in the path // between two Nodes of Binary Search Tree. import java.util.* ; class Node { int data ; Node left right ; Node ( int x ) { data = x ; left = right = null ; } } class GfG { // Insert a new Node in Binary Search Tree static void insertNode ( Node root int x ) { Node current = root parent = null ; // Traverse to the correct // position for insertion while ( current != null ) { parent = current ; if ( x < current . data ) current = current . left ; else current = current . right ; } // Insert new Node at the correct // position if ( parent == null ) root = new Node ( x ); else if ( x < parent . data ) parent . left = new Node ( x ); else parent . right = new Node ( x ); } // Find maximum element in the path from // an ancestor to a node static int maxInPath ( Node root int x ) { int maxElement = Integer . MIN_VALUE ; Node current = root ; // Traverse the path from root to the // target node 'x' while ( current != null && current . data != x ) { maxElement = Math . max ( maxElement current . data ); if ( x < current . data ) current = current . left ; else current = current . right ; } return Math . max ( maxElement x ); } // Find maximum element in the path between two // nodes in BST static int findMaxElement ( Node root int x int y ) { Node current = root ; // Find Lowest Common Ancestor (LCA) of x and y while (( x < current . data && y < current . data ) || ( x > current . data && y > current . data )) { if ( x < current . data && y < current . data ) current = current . left ; else if ( x > current . data && y > current . data ) current = current . right ; } // Find maximum elements in paths from LCA // to x and LCA to y return Math . max ( maxInPath ( current x ) maxInPath ( current y )); } public static void main ( String [] args ) { int [] arr = { 18 36 9 6 12 10 1 8 }; int a = 1 b = 10 ; Node root = new Node ( arr [ 0 ] ); for ( int i = 1 ; i < arr . length ; i ++ ) insertNode ( root arr [ i ] ); System . out . println ( findMaxElement ( root a b )); } }
Python # Python program to find maximum element in the path # between two Nodes of Binary Search Tree. class Node : def __init__ ( self x ): self . data = x self . left = None self . right = None # Insert a new Node in Binary Search Tree def insertNode ( root x ): current = root parent = None # Traverse to the correct position for insertion while current is not None : parent = current if x < current . data : current = current . left else : current = current . right # Insert new Node at the correct position if parent is None : root = Node ( x ) elif x < parent . data : parent . left = Node ( x ) else : parent . right = Node ( x ) # Find maximum element in the path from an # ancestor to a node def maxInPath ( root x ): maxElement = float ( '-inf' ) current = root # Traverse the path from root to the # target node 'x' while current is not None and current . data != x : maxElement = max ( maxElement current . data ) if x < current . data : current = current . left else : current = current . right return max ( maxElement x ) # Find maximum element in the path between # two nodes in BST def findMaxElement ( root x y ): current = root # Find Lowest Common Ancestor (LCA) of x and y while ( x < current . data and y < current . data ) or ( x > current . data and y > current . data ): if x < current . data and y < current . data : current = current . left elif x > current . data and y > current . data : current = current . right # Find maximum elements in paths from LCA to # x and LCA to y return max ( maxInPath ( current x ) maxInPath ( current y )) if __name__ == '__main__' : arr = [ 18 36 9 6 12 10 1 8 ] a b = 1 10 root = Node ( arr [ 0 ]) for i in range ( 1 len ( arr )): insertNode ( root arr [ i ]) print ( findMaxElement ( root a b ))
C# // C# program to find maximum element in the path // between two Nodes of Binary Search Tree. using System ; class Node { public int data ; public Node left right ; public Node ( int x ) { data = x ; left = right = null ; } } class GfG { // Insert a new Node in Binary Search Tree static void insertNode ( Node root int x ) { Node current = root parent = null ; // Traverse to the correct position // for insertion while ( current != null ) { parent = current ; if ( x < current . data ) current = current . left ; else current = current . right ; } // Insert new Node at the correct position if ( parent == null ) root = new Node ( x ); else if ( x < parent . data ) parent . left = new Node ( x ); else parent . right = new Node ( x ); } // Find maximum element in the path from an // ancestor to a node static int maxInPath ( Node root int x ) { int maxElement = int . MinValue ; Node current = root ; // Traverse the path from root to the target node 'x' while ( current != null && current . data != x ) { maxElement = Math . Max ( maxElement current . data ); if ( x < current . data ) current = current . left ; else current = current . right ; } return Math . Max ( maxElement x ); } // Find maximum element in the path between two nodes in BST static int findMaxElement ( Node root int x int y ) { Node current = root ; // Find Lowest Common Ancestor (LCA) of x and y while (( x < current . data && y < current . data ) || ( x > current . data && y > current . data )) { if ( x < current . data && y < current . data ) current = current . left ; else if ( x > current . data && y > current . data ) current = current . right ; } // Find maximum elements in paths from // LCA to x and LCA to y return Math . Max ( maxInPath ( current x ) maxInPath ( current y )); } static void Main () { int [] arr = { 18 36 9 6 12 10 1 8 }; int a = 1 b = 10 ; Node root = new Node ( arr [ 0 ]); for ( int i = 1 ; i < arr . Length ; i ++ ) insertNode ( root arr [ i ]); Console . WriteLine ( findMaxElement ( root a b )); } }
JavaScript // JavaScript program to find maximum element in the path // between two Nodes of Binary Search Tree. class Node { constructor ( x ) { this . data = x ; this . left = null ; this . right = null ; } } // Insert a new Node in Binary Search Tree function insertNode ( root x ) { let current = root parent = null ; // Traverse to the correct position for insertion while ( current !== null ) { parent = current ; if ( x < current . data ) current = current . left ; else current = current . right ; } // Insert new Node at the correct position if ( parent === null ) root = new Node ( x ); else if ( x < parent . data ) parent . left = new Node ( x ); else parent . right = new Node ( x ); } // Find maximum element in the path from an // ancestor to a node function maxInPath ( root x ) { let maxElement = - Infinity ; let current = root ; // Traverse the path from root to the target node 'x' while ( current !== null && current . data !== x ) { maxElement = Math . max ( maxElement current . data ); if ( x < current . data ) current = current . left ; else current = current . right ; } return Math . max ( maxElement x ); } // Find maximum element in the path between // two nodes in BST function findMaxElement ( root x y ) { let current = root ; // Find Lowest Common Ancestor (LCA) of x and y while (( x < current . data && y < current . data ) || ( x > current . data && y > current . data )) { if ( x < current . data && y < current . data ) current = current . left ; else if ( x > current . data && y > current . data ) current = current . right ; } // Find maximum elements in paths from LCA to // x and LCA to y return Math . max ( maxInPath ( current x ) maxInPath ( current y )); } const arr = [ 18 36 9 6 12 10 1 8 ]; const a = 1 b = 10 ; const root = new Node ( arr [ 0 ]); for ( let i = 1 ; i < arr . length ; i ++ ) { insertNode ( root arr [ i ]); } console . log ( findMaxElement ( root a b ));
Izvade
12Izveidojiet viktorīnu
