i trying solve following question geeksforgeeks.com http://www.geeksforgeeks.org/inorder-predecessor-successor-given-key-bst/ using java. getting correct successor while searching keys in tree, values not in tree unable correct successor key.can advise going wrong.
package com.geeksforgeeks.binarysearchtree; public class binarysearchtree { public node root; static class node { int data; node right; node left; public node(int data) { this.data=data; this.right=null; this.left=null; } } public void insert(int data) { root=treeinsert(root,data); } public node treeinsert(node root,int data) { if(root==null) { root=new node(data); return root; } if(data >= root.data) root.right= treeinsert(root.right,data); else root.left= treeinsert(root.left,data); return root; } public void delete(int data) { root=recdelete(root,data); } public node recdelete(node root,int data) { //base case if(root==null)return root; //recurring down tree if(root.data>data) root.left=recdelete(root.left,data); else if(root.data<data) root.right=recdelete(root.right,data); else { if(root.left==null)return root.right; else if(root.right==null)return root.left; root.data= min(root.right); root.right=recdelete(root.right,root.data); } return root; } private int min(node root) { // todo auto-generated method stub int minv=root.data; while(root.left!=null) { minv=root.left.data; root=root.left; } return minv; } public static void main(string[] args) { // todo auto-generated method stub binarysearchtree tree = new binarysearchtree(); /* let create following bst 50 / \ 30 70 / \ / \ 20 40 60 80 */ tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); system.out.println("successor :"+tree.inordersuccessor(50)); tree.delete(20); tree.inorder(); tree.delete(30); tree.inorder(); tree.delete(50); tree.inorder(); } private int inordersuccessor(int i) { node successor=recursiveinordersuccessor(root,i); if(successor!=null) return successor.data; else return -1; } private node recursiveinordersuccessor(node root2,int i) { node successor=null; //if tree empty if(root2==null)return null; //if root key if(root2.data==i) { successor=root2.right; if(root2.right!=null) { while(successor.left!=null) successor=successor.left; } return successor; } node newsuccessor = null; if(root2.data>i) { successor=root2; newsuccessor=recursiveinordersuccessor(root2.left,i); } else { successor=root2; newsuccessor=recursiveinordersuccessor(root2.right,i); } if(newsuccessor==null) return successor; else return newsuccessor; } private void inorder() { // todo auto-generated method stub inorderrecursion(root); } private void inorderrecursion(node root) { // todo auto-generated method stub if(root!=null) { inorderrecursion(root.left); system.out.println(root.data); inorderrecursion(root.right); } } }
you need make change in recursiveinordersuccessor().
- capture successor only when value of current node being traversed greater, i.e. shouldn't capturing node successor in case of
(root2.data < i). - return
nullif reachnulland don't find greater value.
given below changed code. find demo here
private node recursiveinordersuccessor(node root2,int i) { if(root2 == null) return null; node successor = null, succ2 = null; if(root2.data == i) { successor = root2.right; while(successor.left != null){ successor = successor.left; } return successor; } if(root2.data > i){ successor = root2; succ2 = recursiveinordersuccessor(root2.left, i); if(succ2 != null && succ2.data < successor.data) return succ2; else return successor; } else{ return recursiveinordersuccessor(root2.right, i); } } 
Comments
Post a Comment