Q. Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.

**Algorithm:**

**Four cases:**

**Case 1:**Node is root or is the last Node in in-order traversal. (return null).

**Case 2:**Node (1) doesn't have a right child and is the left child of it's parent. (return 2)**Case 3:**Node(4) Does not have a right child and is the right child of it's parent. (return 4)**Case 4:**Node(2) has a right child. (return 7)

Image Source: https://www.cs.usfca.edu/~galles/visualization/BST.html

**1.**Check if there is a right node. If there is a right node, go to it's farthest left and return that node. If there was no left node in the first place, return that right node.

**2.**If there is no right node, go back up. Now if the previous node was a left child, print parent else keep going up.

**3.**If you reach null, there is no left child in the path (in

**Case 1**) print

**null**.

**Source:**

public class Code{ public class Node{ int value; Node left, right, parent; Node(){} Node(int value){this.value = value;} Node(int value, Node left, Node right){ this.value = value; this.left = left; this.right = right; } @Override public String toString(){ return "Value: "+value; } } //Function Required Node getInorderSuccessor(Node node){ if(node == null)return null; Node prev; if(node.right != null){ node = node.right; while(node.left!=null)node= node.left; return node; } prev = node; node = node.parent; while(node!= null && prev!=node.left){ prev = node; node = node.parent; } return node; } Node root; Node test; void makeCustomTree1(){ //Test Case: 1 root = new Node(2); test = root; } void makeCustomTree2(){ //Test Case: 2 test = new Node(1); addChildren(root, test, null); } void makeCustomTree3(){ //Test Case: 3 root = new Node(4); addChildren(root, new Node(2), new Node(5)); test = new Node(3); addChildren(root.left, null, test); } void makeCustomTree4(){ //Test Case: 4 root = new Node(2); test = root; addChildren(root, null, new Node(7)); } void addChildren(Node parent, Node left, Node right){

parent.left = left; parent.right = right; if(left!=null) left.parent = parent; if(right!=null) right.parent = parent; } public static void main(String[] args){ Code tree = new Code(); tree.makeCustomTree1(); System.out.println(tree.getInorderSuccessor(tree.test)); tree.makeCustomTree2(); System.out.println(tree.getInorderSuccessor(tree.test)); tree.makeCustomTree3(); System.out.println(tree.getInorderSuccessor(tree.test)); tree.makeCustomTree4(); System.out.println(tree.getInorderSuccessor(tree.test)); } }

**Output:**

null

Value: 2

Value: 4

Value: 7

## No comments:

## Post a Comment