Find floor value of input data in Binary search tree – DFS / Example

• Given a binary search tree (BST), find out the floorl value of input data using recursive algorithm.
• Traverse the binary search tree, using depth first search algorithm.
• What is floor value in BST?
  • The largest value just smaller or equal to given input data or key.
•  We have already discussed Fnd out Ceil value of input data (BST)

Let us find the ceil value in a binary search tree (BST) shown in Fig 1.

The inorder traversal of binary search tree as shown in Fig 1  is
25 50 75 100 120 125 140 150 160 175 190

Example 1: find floor value of input 90 in a given BST (Fig 2).

• Traverse the binary tree using depth first search algorithm.
• At node A, check 100 > 90 ? floor value may in left subtree.
  • At node B, check 50> 90 ? traverse right subtree.
    • At node E, check 75 > 90 ?, traverse right subtree.
      • Node E is a leaf node, return E to Node B.
  • return Node E to Node A.
• Node A gets Node E from left subtree, Node E (75) is floor value for input 90.

Example 2: find floor value of input 120 in a given BST (Fig 3).

• At node A, check 100 > 120 ? floor value may in right subtree.
  • At node C, check 150> 120 ? traverse left subtree.
    • At node F, check 125 > 120 ?, traverse left subtree.
      • At node H, check 120 == 120 ?, return Node H from here.
    • return Node H to Node C.
  • return Node H to Node A.
• Node A got non null value i.e. Node H from right subtree, Node H (120) is floor value for 120.

Example 3: find floor value of input 126 in a given BST (Fig 3).

We can analyse the Fig 4 like example 1 & example 2.
Let us summarize to find floor values of sample input data in a given BST as follows:

Algorithm: find floor value in binary search tree

• Traverse the binary search tree
  • Node floor(Node root, int data).
• If data of current node equals to input data
  • Current node is floor node for input data
  • return the current node from here
• If data of current node is greater the input data
  • Traverse the left sub tree to find out floor value
• If we are here, we need to find the floor value in right subtree
  • Traverse the right subtree
  • If found value in right subtree
    • return the node got from right subtree
  • Else, return the current node
• By the end of traversal we will get our floor value.

Time complexity of algorithm: O(log(n))

Program: find floor value of input data in Binary search tree.

1.) FloorInBST Class:

• FloorInBST is responsible for finding floor value of BST using depth first search recursive algorithm.

package org.learn.Question;
import org.learn.PrepareTree.Node;

public class FloorInBST {	
	public static Node floor(Node root, int data) {
		if (root == null) 
			return root;
		if (root.data == data) 
			return root;
		if (root.data >  data) 
			return floor(root.left, data);
		Node right = floor(root.right, data); 
		if (right == null) 
			return root;
		else return right; 
	}	
	public static void inorder(Node root) {		
		if(root == null)
			return;
		inorder(root.left);
		System.out.printf("%d ",root.data);
		inorder(root.right);		
	}	
}

2.) Node Class: 

Node class representing the nodes of a binary tree. Node class has following attributes

• Data Node
• left child
• right child

package org.learn.PrepareTree;

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

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}
	public Node() {
		this.left = null;
		this.right = null;
	}
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App Class:

• We are constructing BST in main method.
• We are calling method of FloorInBST class, to find floor value of input data in a BST.

package org.learn.Client;

import org.learn.PrepareTree.Node;
import org.learn.Question.FloorInBST;

public class App 
{
    public static void main( String[] args )
    {  
       //root level 0
       Node A = Node.createNode(100);
       //Level 1
       Node B = Node.createNode(50);
       Node C = Node.createNode(150);
       //Level 2
       Node D = Node.createNode(25);
       Node E = Node.createNode(75);
       Node F = Node.createNode(125);
       Node G = Node.createNode(175);
       //Level 3
       Node H = Node.createNode(120);
       Node I = Node.createNode(140);
       Node J = Node.createNode(160);
       Node K = Node.createNode(190);
             
       //connect Level 0 and 1
       A.left = B;
       A.right = C;
       //connect level 1 and level 2
       B.left = D;
       B.right = E;
       C.left = F;
       C.right = G;
       //Connect level 2 and level 3
       F.left = H;
       F.right = I;
       G.left = J;
       G.right = K;
       
       System.out.println("Inorder Traversal of BST:");   
       FloorInBST.inorder(A);
       int data = 90;       
       Node floor = FloorInBST.floor(A, data);     
       if(null != floor) {
    	   System.out.printf("\nFloor value of %d is %d",data,floor.data);
       }       
       data = 120;       
       floor = FloorInBST.floor(A, data);     
       if(null != floor) {
    	   System.out.printf("\nFloor value of %d is %d",data,floor.data);
       }       
       data = 170;       
       floor = FloorInBST.floor(A, data);     
       if(null != floor) {
    	   System.out.printf("\nFloor value of %d is %d",data,floor.data);
       }             
    }
}

Output: find floor value of input data in Binary search tree:

Inorder Traversal of BST:
25 50 75 100 120 125 140 150 160 175 190
Floor value of 90 is 75
Floor value of 120 is 120
Floor value of 170 is 160

Download code – find floor value in BST DFS recursive