Home » Binary Search Tree » Find Inorder successor of a Node in BST

Find Inorder successor of a Node in BST

in - on 11:54:00 - No comments

Find Inorder successor of a Node in BST.

Inorder traversal of a Binary Tree reads a Left most element first then a middle or root element and at last the right most element, so when we say successor of a Node, you have to return the next element of the Node in Inorder traversal.
 
Consider a below BST,

         50
       /    \
      /      \
     30       70
   /   \     /  \
  20   40   60  80
 /  \
10  25

Example:
Inorder Successor of Node 50 is 60
Inorder Successor of Node 25 is 30
Inorder Successor of Node 40 is 50
Inorder Successor of Node 80 is null
Inorder Successor of Node 70 is 80

Inorder traversal of a Binary Search Tree always return the data in sorted order. So one way to find is to do a Inorder traversal which would be 

10 20 25 30 40 50 60 70 80

and then you can sequentially search for the next element of the given node which is Inorder successor of a Node. this approach would have O(n) time and space complexity. lets optimize it to O(h) where h is height of tree. (Note: in case of skewed tree it will still be O(n)) 

Inorder Successor In BST
There are 2 case in finding Inorder successor of a Node in BST.

  • Given Node has Right Subtree
  • Given Node doesn't has right subtree

Given Node has Right Subtree, 


In this case, Node 50 has right subtree so the next element would obviously be the left most element in the right sub tree as that how Inorder traversal goes.

Given Node doesn't has right subtree,

In this case (Node 22), where there is no right sub tree, so the next element that is read in inorder successor is the root node 25 and the root node will always encountered when you visit left of any node (this is what is in-order traversal you first visit left most node, so if there is a node and it has left node, you will first visit that and then the root node.)

In above tree, we visited left side 3 times, one from Node 50, one from Node 30 and one from Node 25, so the last left taken is the answer which in this case is 25.

Consider Node 40, the last left you will take is only from Node 50, so Inorder successor of 40 is Node 50.

Inorder successor of Binary Search Tree in Java.
package javabypatel.bst;

public class InOrderSuccessor {
    public static void main(String[] args) {
        new InOrderSuccessor();
    }

    public InOrderSuccessor() {
        Node rootNode = null;
        rootNode = addNode(rootNode, 50);
        rootNode = addNode(rootNode, 30);
        rootNode = addNode(rootNode, 70);
        rootNode = addNode(rootNode, 20);
        rootNode = addNode(rootNode, 40);
        rootNode = addNode(rootNode, 10);
        rootNode = addNode(rootNode, 25);
        rootNode = addNode(rootNode, 60);
        rootNode = addNode(rootNode, 80);

        System.out.println(inorderSuccessor(rootNode, 70, null).getData());
    }

    private Node inorderSuccessor(Node root, int k, Node lastLeftNodeVisited) {
        if (root == null) {
            return root;
        }

        if (root.getData() == k) {
            if (root.getRight() != null) {
                return findSmallestInLeft(root.getRight());
            } else {
                return lastLeftNodeVisited;
            }
        }

        if (k < root.getData()) {
            return inorderSuccessor(root.getLeft(), k, root);
        } else {
            return inorderSuccessor(root.getRight(), k, lastLeftNodeVisited);
        }
    }

    private Node findSmallestInLeft(Node root) {
        if (root == null || root.getLeft() == null) {
            return root;
        }

        return findSmallestInLeft(root.getLeft());
    }

    private Node addNode(Node rootNode, int i) {
        if (rootNode == null) {
            return new Node(i);
        } else {
            if (i > rootNode.getData()) {
                Node nodeToAdd = addNode(rootNode.getRight(), i);
                rootNode.setRight(nodeToAdd);

            } else {
                Node nodeToAdd = addNode(rootNode.getLeft(), i);
                rootNode.setLeft(nodeToAdd);
            }
        }
        return rootNode;
    }
}

 
package javabypatel.bst;

public class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

Categories:

Post a Comment