Editing Binary search tree (section)

====Successor and predecessor====
For certain operations, given a node <math>\text{x}</math>, finding the successor or predecessor of <math>\text{x}</math> is crucial. Assuming all the keys of a BST are distinct, the successor of a node <math>\text{x}</math> in a BST is the node with the smallest key greater than <math>\text{x}</math>'s key. On the other hand, the predecessor of a node <math>\text{x}</math> in a BST is the node with the largest key smaller than <math>\text{x}</math>'s key. The following pseudocode finds the successor and predecessor of a node <math>\text{x}</math> in a BST.<ref>{{cite web|url=https://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-url=https://web.archive.org/web/20210413045057/http://ranger.uta.edu/~huang/teaching/CSE5311/CSE5311_Lecture10.pdf|archive-date=13 April 2021|page=12|publisher=[[University of Texas at Arlington]]|access-date=17 May 2021|url-status=live|title=Design and Analysis of Algorithms|author=Junzhou Huang}}</ref><ref>{{cite web |author=Ray |first=Ray |title=Binary Search Tree |url=https://cs.lmu.edu/~ray/notes/binarysearchtrees/ |access-date=17 May 2022 |publisher=[[Loyola Marymount University]], Department of Computer Science}}</ref><ref name="algo_cormen" />{{rp|292–293}}
{|
|- style="vertical-align:top"
|
  BST-Successor(x)
      '''if''' x.right &ne; NIL '''then'''
          '''return''' BST-Minimum(x.right)
      '''end if'''
      y := x.parent
      '''while''' y &ne; NIL '''and''' x = y.right '''do'''
          x := y
          y := y.parent
      '''repeat'''
      '''return''' y
|
  BST-Predecessor(x)
      '''if''' x.left &ne; NIL '''then'''
          '''return''' BST-Maximum(x.left)
      '''end if'''
      y := x.parent
      '''while''' y &ne; NIL '''and''' x = y.left '''do'''
          x := y
          y := y.parent
      '''repeat'''
      '''return''' y
|}
Operations such as finding a node in a BST whose key is the maximum or minimum are critical in certain operations, such as determining the successor and predecessor of nodes. Following is the pseudocode for the operations.<ref name="algo_cormen" />{{rp|291–292}}
{|
|- style="vertical-align:top"
|
  BST-Maximum(x)
      '''while''' x.right &ne; NIL '''do'''
          x := x.right
      '''repeat'''
      '''return''' x
|
  BST-Minimum(x)
      '''while''' x.left &ne; NIL '''do'''
          x := x.left
      '''repeat'''
      '''return''' x
|}