Results 1 to 2 of 2
  1. #1
    Adhene is offline Member
    Join Date
    Apr 2016
    Posts
    1
    Rep Power
    0

    Default Understanding how Successors and Predecessors work in code.

    Hello everyone!
    I know how to find Successors and Predecessors in a Binary Search Tree but I'm having a small problem understanding how they work in coding.
    The following code works perfectly but could someone explain to me what happens in each step.Thanks in advance.
    Java Code:
    package inordersuccessorpredecessor;
     
     
    public class InorderSuccessorPredecessor {
     
       static int successor, predecessor;
     
        public void successorPredecessor(Node root, int val) {
            if (root != null) {
                if (root.data == val) {
     
                    if (root.left != null) {
                        Node t = root.left;
                        while (t.right != null) {
                            t = t.right;
                        }
                        predecessor = t.data;
                    }
                    if (root.right != null) {
     
                        Node t = root.right;
                        while (t.left != null) {
                            t = t.left;
                        }
                        successor = t.data;
                    }
                } else if (root.data > val) {
                    successor = root.data;
                    successorPredecessor(root.left, val);
                } else if (root.data < val) {
     
                    predecessor = root.data;
                    successorPredecessor(root.right, val);
                }
            }
        }
     
       public static void main(String args[]) {
            Node root = new Node(20);
            root.left = new Node(10);
            root.right = new Node(30);
            root.left.left = new Node(5);
            root.left.left.right = new Node(7);
            root.left.right = new Node(15);
            root.right.left = new Node(25);
            root.right.right = new Node(35);
            root.left.right.left = new Node(13);
            root.left.right.right = new Node(18);
            InorderSuccessorPredecessor i = new InorderSuccessorPredecessor();
            i.successorPredecessor(root, 10);
            System.out.println("Inorder Successor of 10 is : " + successor
                    + " and predecessor is : " + predecessor);
            i.successorPredecessor(root, 30);
            System.out.println("Inorder Successor of 30 is : " + successor
                    + " and predecessor is : " + predecessor);
        }
    }
    class Node {
        int data;
        Node left;
        Node right;
     
        public Node(int data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    29

    Default Re: Understanding how Successors and Predecessors work in code.

    For a binary search tree (L, n, R) where L and R are the left and right sub trees of a node n, the predecessor of node n is the largest element in sub tree L and the successor is the smallest element in sub tree R.
    A largest element of a tree is a rightmost element of the tree; if a node doesn't have a left sub tree, it is the smallest element in the tree. A similar reasoning applies for a smallest element of a tree.

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

Similar Threads

  1. Help Understanding this simple code
    By fermon in forum New To Java
    Replies: 6
    Last Post: 11-13-2014, 04:14 AM
  2. Help in Understanding the code
    By CodeX Pro in forum New To Java
    Replies: 17
    Last Post: 05-19-2013, 08:32 AM
  3. Understanding Problem in Code !
    By Jack_Tauson_Sr in forum New To Java
    Replies: 3
    Last Post: 03-25-2013, 03:20 AM
  4. Need help understanding steganography code
    By nrott in forum New To Java
    Replies: 3
    Last Post: 02-04-2012, 12:20 PM
  5. need help understanding part of code
    By mustachMan in forum New To Java
    Replies: 7
    Last Post: 02-09-2011, 08:11 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •