Monday, 1 April 2019

Find largest number in Binary Search Tree which is less than or equal to N

Largest number in Binary Search Tree which is less than or equal to N.

We have a binary search tree and a number N. Our goal is to find the greatest number in the binary search tree that is less than or equal to N. Print -1 if the the value of the element doesn't exists.

We have to find the largest number inside the binary search tree that is smaller than or equal to the target number N.

 Lets see sample input and output:

Algorithm 

We will see Iterative and Recursive algorithm for this.

Iterative Solution:
Note: We will only find our solution while moving towards right as that is where root node(current node may be second highest, store it) is lesser than N and we are searching for higher value equal
to N.

We will never get second highest when we move towards left as that will be the case when root node(current node is greater and we are not interested in greater and we are looking for second highest which should be smaller than N) is greater than N and we are searching for lower value equal to N.

Recursive Solution:
In Recursive solution when we encounter the value lesser than N we will store it in variable secondHighest as that may be second lowest element than N.

When we encounter value which is greater than already stored value in secondHighest and value is less than N, than this is the element which is close to second highest so override secondHighest to current value, continue searching for the item N and our second highest would be in secondHighest variable.

Java program to find largest number in Binary Search Tree which is less than or equal to N.

package com.javabypatel.binarytree;

import com.binarytree.Node;

public class LargesNumberInBSTWhichIsLessThanOrEqualToN {

    public static void main(String[] args) {
        int N = 30;

        // creating following BST
        /*
                 5
                / \
             2      12
            / \     / \
           1  3    9  21
                     / \
                    19 25
        */

        Node rootNode = null;
        rootNode = addNode(rootNode, 5);
        rootNode = addNode(rootNode, 2);
        rootNode = addNode(rootNode, 12);
        rootNode = addNode(rootNode, 1);
        rootNode = addNode(rootNode, 3);
        rootNode = addNode(rootNode, 9);
        rootNode = addNode(rootNode, 21);
        rootNode = addNode(rootNode, 19);
        rootNode = addNode(rootNode, 25);

        System.out.println(findMaxValueLessThanN(rootNode, N));
        System.out.println(findMaxValueLessThanN(rootNode, N, -1));
    }

    //Iterative Solution
    public static int findMaxValueLessThanN(Node root, int n) {
        int val = -1;
        while(root != null) {
            if(root.getData() > n) {
                //When you go towards left of root node, it means current value is greater than N,
                //No need to take backup as current node is > N and you need value less than N.
                //Note: when you move towards right that is the only case your current node is lower than N and
                //you are searching for higher node and we are already taking backup at that time.
                root = root.getLeft();
            } else {
                //When you go towards right of root node, it means you will be moving towards higher value compared to current one,
                //Take the backup of current one as that may be second highest.
                val = root.getData();
                root = root.getRight();
            }
        }
        return val;
    }

    //Recursive Solution
    //take backup in secondHighest when you encounter the value smaller than N.
    //Now replace secondHighest only if you encounter value greater than secondHighest and less than N or
    //when root data is same as N.
    private static int findMaxValueLessThanN(Node root, int N, int secondHighest) {
        if(root == null){
            return secondHighest;
        }

        if ((root.getData() > secondHighest && root.getData() < N) || root.getData() == N) {
            secondHighest = root.getData();
        }

        if(N > root.getData()) {
            return findMaxValueLessThanN(root.getRight(), N, secondHighest);
        } else {
            return findMaxValueLessThanN(root.getLeft(), N, secondHighest);
        }
    }

    //Another way (largestNumber will be initialized with -1 by the caller as indication that number is not present)
    private int findLargestNumberInBSTLessThanOrEqualTo(Node root, int number, int largestNumber) {
	  if (root == null) {
		  return largestNumber;
	  }

	  if (root.getData() == number) {
	  	  return number;
	  }

	  if (number > root.getData()) {
		  return findLargestNumberInBSTLessThanOrEqualTo(root.getRight(), number, root.getData());
	  } else {
	  	  return findLargestNumberInBSTLessThanOrEqualTo(root.getLeft(), number, largestNumber);
	  }
    }

    private static 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;
    }
}
Node.java 
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;
    }
}
at

No comments:

Post a Comment