- Given a binary search tree (bst), we would like to find out K smallest element in BST.
- Traverse the binary search tree using depth first search (DFS) recursive algorithm.
- Perform InOrder binary tree traversal to find smallest K smallest element.
- InOrder tree traversal prints elements in sorted order.
- We can find out K smallest from sorted order result.
- We will use of properties of binary search tree to find k smallest element.
Example: find Kth smallest element in binary search tree.
- Traverse the binary tree using inorder tree traversal algorithm.
- The inOrder traversal of binary tree is as follows:
- Visit left child
- Visit current node or parent node
- Visit right child
The Inorder traversal of binary search tree is:
25 50 75 100 120 125 140 150 160 175 190
K value | Output value |
---|---|
1 | 25 |
3 | 75 |
5 | 120 |
8 | 150 |
Algorithm to find K Smallest Element in BST (DFS/recursive).
- Pass K representing the element (Kth smallest element in BST)
- Array representing the number of element visited [int arr[] = {0}]
- We have wrapped the integer to array
- Pass integer as array object.
- So that we can use its reference in recursive call
- In recursive call keeping track of this integer
- We have used it to compare with K
- Perform InOrder tree traversal (DFS traversal)
- Whenever we found arr[0] == K
- We found the Kth element
- Start returning from recursive call
- At the end of loop, we will get the K Smallest element in BST.
- Time Complexity: O(n)
Program – find K smallest element in binary search tree (recursive algorithm)
1.) KSmallestElement Class:
- KSmallestElement class performs Inorder traversal of binary search tree to find out Kth smallest element.
package org.learn.Question; import org.learn.PrepareTree.Node; public class KSmallestElement { public static Node kSmallestElement(Node root, int k, int[] iElement) { if(null == root) { return root; } Node left = kSmallestElement(root.left, k, iElement ); if(null != left) { return left; } iElement[0] ++; if(iElement[0] == k) { return root; } return kSmallestElement(root.right,k, iElement); } }
2.) App Class:
- We are creating the binary search tree in main method.
- We will invoke method of KSmallestElement class to find out Kth smallest element in a binary search.
package org.learn.Client; import org.learn.PrepareTree.Node; import org.learn.Question.KSmallestElement; 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; int arr[] = {0}; int k = 3; Node element = KSmallestElement.kSmallestElement(A,k,arr); if(null != element) System.out.printf("Smallest element K = %d is %d ",k,element.data); else { System.out.printf("No element found for K = %d",k); } arr[0] = 0; k = 5; element = KSmallestElement.kSmallestElement(A,k,arr); if(null != element) System.out.printf("\nSmallest element K = %d is %d ",k,element.data); else { System.out.printf("No element found for K = %d",k); } } }
3.) Node Class:
- Node class representing the nodes of a binary tree.
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); } }
Output – K smallest element in binary search tree (depth first search)
Smallest element K = 3 is 75 Smallest element K = 5 is 120
Download Code – K Smallest Element in Binary serach tree – DFS