logo

TechCodeview

Çeşitli

BST'nin iki düğümü arasındaki maksimum öğe

BST'nin iki düğümü arasındaki maksimum öğe

Bir dizi göz önüne alındığında N elemanlar ve iki tam sayı bir b verilen diziye ait olanlar. Bir oluştur İkili Arama Ağacı elemanları ekleyerek arr[0]'dan arr[n-1]'e . Görev bulmaktır maksimum a'dan b'ye giden yoldaki öğe.

Örnek:

Giriş : varış[] = { 18 36 9 6 12 10 1 8 } a = 1 b = 10.
Çıkış : 12



BST

Açıklama: Yol: 1'den 10'a içerir { 1 6 9 12 10 } . Maksimum eleman 12'dir.

İçerik Tablosu

[Saf yaklaşım] Hashing kullanma - O(n * log n) Zaman ve O(n) Uzay

Fikir bir kullanmaktır hash haritası depolamak için ebeveyn her düğümün düğümü ikili arama ağacı . Her iki verilen düğümden başlayabilir ve karşılaşılan düğümleri saklayan ağaçta yukarıya doğru gidebiliriz. ayarlamak . İki düğümün köküne veya ortak atasına ulaştığımızda, her düğümden ağaçta aşağıya doğru ilerleyebilir ve maksimum düğüm kümesinde karşılaşılan öğe.

Yukarıdaki yaklaşım için algoritma adımları:

  • Boş oluştur karma tablosu depolamak için ebeveyn İkili arama ağacındaki her düğümün düğümü.
  • Bir gerçekleştirin derinlik öncelikli arama (DFS) ikili arama ağacının geçişini yapın ve karma tablosunu her düğümün ana düğümüyle doldurun.
  • İki işaretçiyi başlat diyor p1 ve p2 verilen düğümlere.
  • İki boş kümeyi başlat diyorlar s1 ve s2 ağaçtan yukarıya doğru giderken karşılaşılan düğümleri depolamak için p1 ve p2 sırasıyla.
  • Sırasında p1 ve p2 öyle eşit değil aşağıdakileri yapın:
    • p1 değilse hükümsüz s1'i ayarlamak için ekleyin ve güncelleme p1'i karma tablosunu kullanarak üst düğümüne aktarın.
    • p2 değilse hükümsüz s2'yi ayarlamak için ekleyin ve güncelleme p2'yi karma tablosunu kullanarak üst düğümüne aktarın.
  • kesişim kümesini bulun s1 ve s2 yani hem s1 hem de s2 için ortak olan düğümler kümesi.
  • Bu kavşakta bul maksimum öğeyi seçin ve geri gönderin.

Yukarıdaki yaklaşımın uygulanması aşağıdadır:

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  ));

Çıkış 
12

[Beklenen yaklaşım] İki düğümün LCA'sını kullanma - O(h) Zaman ve O(h) Uzay

Fikir bulmaktır En Düşük Ortak Ata 'a' düğümü ve 'b' düğümü. Daha sonra LCA ile 'a' arasındaki maksimum düğümü arayın ve ayrıca LCA ile 'b' arasındaki maksimum düğümü bulun. Cevap maksimum iki düğüm olacaktır.

Yukarıdaki algoritmanın uygulaması aşağıdadır:

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  ));

Çıkış 
12
Test Oluştur

Paylaşmak

Hoşunuza Gidebilir

Çekirdek Nedir?

Çekirdek Nedir?

Python Yeni Hat

Python Yeni Hat

En Makaleler

Kategori

Blog Java Dönüşümü Matematik Java Koleksiyonları Farklılıklar Java Dizesi

Ilginç Haberler