Print last K nodes of binary search tree

Print last K nodes of binary search tree

As we are all aware of that binary search tree possesses a special property where all nodes on left side of a given node are smaller and all nodes on right side are greater than it. And we we also know how to traverse a binary search tree in various orders like pre, post or inorder. Today, we are going to talk about a problem which can be solved by slightly tweaking the way a BST is traversed. Problem at hand is : Find and print last k nodes of a binary search tree.

For example, last 4 nodes of this BST will be: 45,40,37,30
Last K nodes of BST

Print last K elements of Binary Search Tree.

To arrive at the solution of this problem, let’s start with some basic questions.How do we print all nodes of binary search tree? Any traversal pre, in or post order traversal would do that.
To find last K nodes of a BST, we need to traverse tree in some sorted order. So, next question to be asked is: what if we need nodes in sorted order? And the answer is inorder traversal of BST will do that.

What we do in inorder traversal of a tree? We traverse left child of node at hand, then node itself, and then right child of node. It gives us nodes in sorted in increasing order.
Now, since problem talks about last K nodes, some how we need all nodes to in decreasing order, whereas plain vanilla inorder traversal gives nodes in increasing order. That’s a no problem. Reverse inorder.

Traverse right node, parent node and then at last left node.Now what is condition in the question?  We need to traverse only K nodes in reverse sorted order, so stop as soon as you have visited K nodes.

Fine do some book keeping and you will get the solution. Below is the code for the same.
This algorithm can be used to solve multiple other problems like, find Kth largest node, Kth smallest node in BST etc.

Print last K nodes of BST implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;

void printKNodes(Node * node, int *K){
	if(node == NULL || (*K) == 0) return;
 
	print_k_nodes(node->right, K);
	printf("%d ", node->value);
        (*K)--;
	print_k_nodes(node->left, K);
}
 
void inorder(Node * root){
	if ( !root ) return;
 
	inorder(root->left);
	printf("%d ", root->value );
	inorder(root->right);
}
 
Node * createNode(int value){
        Node * newNode =  (Node *)malloc(sizeof(Node));
        newNode->value = value;
        newNode->right= NULL;
        newNode->left = NULL;
        return newNode;
}

Node * addNode(Node *node, int value){
        if(!node)
           return createNode(value);
        else{
           if (node->value > value)
                node->left = addNode(node->left, value);
           else
                node->right = addNode(node->right, value);
        }
        return node;
}
 
/* Driver program for the function written above */
int main(){
        Node *root = NULL;
        Node * last = NULL;
        Node *ptrToHead = NULL;

        //Creating a binary tree
        root = addNode(root,30);
        root = addNode(root,20);
        root = addNode(root,15);
        root = addNode(root,25);
        root = addNode(root,40);
        root = addNode(root,37);
        root = addNode(root,45);
 
        int K =4;
        printKNodes(root, &K);
        return 0;
}

Worst case complexity can be O(N), if BST is completely skewed towards right, else O(K) as we would be traversing only K nodes.

This is classic problem asked in many big companies. It is easy to solve and code in limited time period which we have in interview and tests binary search tree understanding of candidate.

I will be adding more post on such problems, please share if you have any in mind. I would love to solve those.

  • Hafeez

    The logic under ‘Print last K elements of Binary Search Tree’ is wrong. It prints all the elements of a binary search tree.

    Corrected code to add an extra check for k > 0 before printing.

    https://github.com/hafeezpk/algos/blob/master/src/BinaryTree.java

    • http://algorithmsandme.com/ Jitendra Sangar

      Just check again, as it prints only last K elements of the tree. I have uploaded the combined code. You can directly run in ideone.com

    • http://algorithmsandme.com/ Jitendra Sangar

      Just check again, as it prints only last K elements of the tree. I have uploaded the combined code. You can directly run in ideone.com