BST: inOrder преемник и предшественник

Question

Они выглядят правильными? Я их реализовал и искал для их просмотра.

Node predecessor(Node node) { 
    if ((node.left == null) && (node.right==null)) { 
     return node; 
    } 
    if (node.right != null) { 
     return predecessor(node.right); 
    } 
    if (node.left != null) { 
     return predecessor(node.left); 
    } 
} 


Node successor(Node node) { 
    if ((node.left == null) && (node.right==null)) { 
     return node; 
    } 
    if (node.left != null) { 
     return successor(node.left); 
    } 
    if (node.right != null) { 
     return successor(node.right); 
    } 
} 

Answer 1

Нет, они не верны. Предшественник узла не может находиться в правом поддереве. Преемник узла не может находиться в левом поддереве.

Answer 2

//O(h) time complexity..... 
    public static TreeNode GetSuccessorInorder(TreeNode root, TreeNode toFind) 
    { 
     if (root == null) return null; 

     //If right sub-tree is not null - get the min of right sub-tree... 
     //If the right subtree of node x is nonempty, then the successor of x is just the left-most node in the right subtree 
     if (toFind.right != null) 
     { 
      TreeNode rootRightSubtree = toFind.right; 
      TreeNode curr = rootRightSubtree; 

      //The left-most node in the right-subtree is always the minimum..... 
      while (curr != null) 
       curr = curr.left; 

      return curr; 
     } 
     //If right sub-tree is null - Do in-order search and keep track of last traversed parent.. ;-) 
     //If the right subtree of node x is empty and x has a successor y, then y is the lowest ancestor of x whose 
     //left child is also an ancestor of x. 
     else 
     { 
      TreeNode succ = null; 

      // Start from root and search for successor down the tree 
      while (root != null) 
      { 
       //in-order tree walk....      
       if ((int)toFind.data < (int)root.data) 
       { 
        succ = root; 
        root = root.left; 
       } 
       else if ((int)toFind.data > (int)root.data) 
        root = root.right; 
       else 
        break; 
      } 

      return succ; 
     } 
    } 

Answer 3

Inorder sucessor in BST.. 
private TreeNode treeInorderSuccessor(TreeNode root, int data) { 
    System.out.println("called"); 
    TreeNode keyNode = searchTreeNode(root, data); 
    if(keyNode == null){ 
     return keyNode; 
    }else{ 
     if(keyNode.right != null){ 
      root = findMinFromRight(keyNode.right); 
      return root; 
     }else{ 
      TreeNode suc = null; 
      TreeNode anc = root; 
      while(anc != keyNode){ 
       if(anc.data > keyNode.data){ 
        suc = anc; 
        anc = anc.left; 
       }else{ 
        anc = anc.right; 
       } 
      } 
      return suc; 
     } 
    } 
} 
private TreeNode searchTreeNode(TreeNode root, int data) { 
    if(root == null){ 
     System.out.println("node not found"); 
    }else{ 
     if(root.data == data){ 
      System.out.println("node found"); 
     }else if(root.data >= data){ 
      root = searchTreeNode(root.left, data); 
     }else if(root.data < data){ 
      root = searchTreeNode(root.right, data); 
     } 
    } 
    return root; 
} 

private TreeNode findMinFromRight(TreeNode node) { 
    while(node.left != null){ 
     node = node.left; 
    } 
    return node; 
}