Lowest common ancestor with Range Minimum Query

Lowest common ancestor with Range Minimum Query

We already have discussed least common ancestor and range minimum query. In this post, we will discuss how to use RMQ to find Least common ancestor of two given nodes.  This is post will concentrate on finding Lowest common ancestor with Range Minimum Query. LCA of (u,v) is the node which is furthest from root and u and v are descendent of it. For example, LCA of (5,9) is 2.

LCA using RMQ

In earlier solutions, we were scanning tree each time a query if fired to find LCA of two nodes which has complexity of O(n). If this query if fired frequently, this operation may become bottleneck. One way to avoid processing all nodes when LCA is asked, is to preprocess tree and store that information in such a way that LCA can be found instantly, say in O(1).

This pattern is very similar to Range Query Minimum algorithm. Can we reduce lowest common ancestor problem to range query minimum problem?

Reduction of LCA to RMQ

Let’s revise what is RMQ : Given array A of length n.  RMQA(i,j) – returns the index of the smallest element in the subarray A[i..j].  Suppose an algorithm has:  Preprocessing time –  Query time –  Notation for the overall complexity of an algorithm: <f(n), g(n) >.

Let’s find LCA of two nodes 5 and 8 manually in above graph. We notice that LCA(u,v) is shallowest common node (in terms of distance from root) which is visited when u and v are visited using depth first search of tree.  Important thing to note is that we are interested in shallowest, which is minimum depth, node between u and v. Sounds like RMQ?

Implementation wise, tree is traversed as Euler tour. At most there can be 2n-1 nodes in Euler tour of tree, store this tour in an array of  2n-1. Then we require depth of each node while doing Euler tour, so we store this information in another arrays of size 2n-1. Any depth would do as far as consistency is maintained, but we will store depth when node was visited first.

1. Euler Tour [1,..,2n-1] – The nodes visited in an Euler tour of T. Euler[i] is the label of the ith node visited in the tour. 
2. Depth[1,..2n-1] – The level of the nodes tour. Level[i] is the level of node Euler[i]. (level is defined to be the distance from the root).
3. FirstVisited[1,..n] – FirstVisited[i] will hold value when node is first visited.

For example of this computation

lowest common ancestor using range minimum query example

To compute LCA(u,v):  All nodes in the Euler tour between the first visits to u and v are E[FV[u],..,FV[v]] (assume FV[u] < FV[v]). 

The shallowest node in this sub-tour is at index RMQ D(FV[u],FV[v]), since D[i] stores the depth of node at E[i]. 

RMQ will return index of shallowest node between u and v, thus output node will be E[RMQ D(FV[u],FV[v])] as LCA(u,v)

lca using rmq example

lowest common ancestor using range minimum query implementation

Beauty of this algorithm to find lca using rmq is that it can be used to find LCA of any tree not just only binary tree or BST. Complexity of algorithm to find lowest common ancestor using range minimum query is <O(n), O(1)> with additional space complexity of O(n).

Please share if there is something wrong or missing, we would love to hear from you. If you are interest in contributing to algorithms and me,please refer to publisher page.

Replace node with sum of all greater node in binary search tree

Today, we will see a problem, solution to which uses traversal of tree in a bit different manner. Problem statement is : Replace a node with sum of all nodes which are greater than it. First question which comes to mind is : what should be done with rightmost child of tree? Should it remain as such or replaced with zero as there is node greater than it? Based on clarification, we can design our solution. In our case, for simplicity, we will replace right most node with zero.

Example : Original tree

replace with sum of greater nodes

After replace nodes with sum of all greater nodes.

replace node with sum of greater nodes

How can we solve it? Easiest way is to do inorder traversal of BST and store that into an array. Now, starting from end of array, replace element of array with sum of all elements on the right. With bit of trick, this algorithm works in O(N) time, however, uses two traversals of tree and O(N) extra space.

We know that inorder traversal of BST gives nodes in sorted in ascending order. Since, we need to visit greater nodes before the node in order to calculate their sum, can we just have nodes of BST visited in sorted but in descending order.

How about reversing the inorder traversal itself? In this, traverse right subtree first, then node and at last left subtree. When right subtree is traversed for a node, we are actually traversing all node which are greater that node, all we need to do is return sum from that traversal. While traversing left subtree, we have to just propagate sum of right subtree and node.

Solution can be implemented using recursion with base case being right most node of tree. If we reached right most tree,  replace it with zero and return the value of the node to parent.

Implementation of replacing a node with sum of all greater nodes

Complexity of algorithm to replace node with sum of all nodes greater than it, is O(N) with no extra space.

Subtree of binary search tree implementation

subtree of binary search tree

We learned basics of binary search tree and it’s properties and attributes. Today, we will discuss an interesting problem : to find if a given BST is subtree of binary search tree? When does tree becomes subtree of binary search tree? When  all nodes in smaller tree are present in bigger one and in the same order, then we call smaller tree as subtree of bigger tree.

Below figures define what qualifies as subtree and not a subtree

subtree of binary search tree
S is not subtree of tree T
subtree of binary search tree example
S is subtree of T

To find if a tree is subtree of a given tree, we have to find where does subtree lies in bigger tree. Start with roots of both trees and check nodes are equal, if yes, check if left subtree and right subtree of smaller tree are identical to left subtree and right subtree of bigger tree.

If nodes are not equal or any of the subtree is not identical, we move down to left or right of bigger tree and start the process again.

In this procedure, we are comparing root first, then left subtree and in last right subtree. It’s a preorder traversal. There are two preorder traversal involved. One of the bigger tree for selecting the candidate root and other of both trees simultaneously to check if they are identical. While traversing, instead of printing nodes, compare them and see if they are identical or not. Please refer : how to check if two trees are identical or not?

Algorithm to find if tree is subtree of binary search tree

1. Start from root of tree1 and tree2 call them currentNodes
2. If both are null, return true
3. Check if currentNodes are identical?
   3.1 Check if data in currentNodes of both tree is equal.
   3.2 Recursively, check if left and right subtree are identical
   3.3 If 3.1 and 3.2 are true, return true else false
4. If currentNodes are not identical
   4.1 Move down to left subtree of tree1 and repeat 3
   4.2 Move down to right subtree of tree1 and repeat 3

Below is the modified preorder traversal of tree which does the trick for us.

Subtree of binary search tree : Implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
#define true 1
#define false 0
#define MAX(a,b)  (a < b ? b : a)
 
 int isIdenticalBST(Node *node1, Node *node2){
	if(!node1 && !node2) return true;
 
	if(!node1 || !node2) return false;
 
	return (node1->value==node2->value 
			&& isIdenticalBST(node1->left, node2->left)
			&& isIdenticalBST(node1->right, node2->right));
}
 
int isSubtree(Node *node1, Node * node2){
	if(!node1) return false;
	if(!node2) return true;
 
	if (isIdenticalBST(node1, node2)) return true;
 
	return isSubtree(node1->left, node2) 
               || isSubtree(node1->right, node2);
}
 
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);
	}
	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;
	//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, 38);
	root = addNode(root, 39);
	root = addNode(root, 45);
 
	Node *root2 = NULL;
	root2 = addNode(root2, 40);
	root2 = addNode(root2, 35);
	root2 = addNode(root2, 39);
	root2 = addNode(root2, 45);
	int height = 0;
	printf( "Is tree subtree : %s", 
		isSubtree( root, root2 ) ? "Yes" : "No" );
 
	return 0;
}

Complexity of algorithm to find if a tree is subtree of binary search tree is O(mn) where m and n are nodes in smaller and bigger tree.

There is another way, it can be done in O(n) complexity where inorder and preorder traversals of two trees are stored in arrays. Check if inorder traversal of smaller tree is subarray of inorder traversal of larger tree and check if preorder traversal of smaller tree is subarray of preorder traversal bigger tree.

If above conditions are true, tree is subtree of larger tree else not. However, we require O(n) extra space.

Why we need to compare two traversals and not only one? Because at least two traversals of tree are required to uniquely define a binary tree.

Please share if there is something wrong or missing. We would love to hear from you. If you want to contribute to website, please contact us and earn money.

Height balanced binary search tree

Height balanced binary search tree

In last post, we discussed what is height of tree and how to find height of tree. In this post, we will use that information to find if tree is height balanced binary search tree or not?  A tree is called as balanced tree if difference between height of left and right subtree is at most 1 at every node.So, if tree rooted at node let’s r, height of left subtree l and height of right subtree r, should not differ more than 1.

For example, below tree is balanced

height balanced binary search tree

where as this tree is not.

not height balanced search tree

Worst case complexity of algorithms running on balanced tree is O( log N ) where as on non balanced tree it will be O(N).

How to find if tree is balanced binary search tree?

To find answer to bigger problem, we need to find that all subtrees are also balanced. Idea is to find if left and right subtree are balanced, then check if difference between height of left and right subtree is at max 1. If any of these conditions is false, tree is not balanced.

We can solve this problem using bottom up approach. Go all the way to leaf and then check if leaf node is balanced. Then return height of left and right subtree to parent and check if parent is balanced, go on till you reach root.

Algorithm to find if tree is balanced is height balanced binary search tree

1. Start from root
2. For each node of tree.
   2.1 Find height of left subtree, call it lheight
   2.2 Find height of right subtree, call it rheight
   2.3 If difference between lheight and rheight is 1, return true
   2.4 Else return false.

Height balance binary search tree check implementation

Complexity of algorithm to find if tree is height balanced binary search tree or not is O(N2) as we have to visit each node of tree at least once and find height of left and right subtree which takes O(N).

Working of algorithm can be understood easily by looking at this figure.

height balance binary search tree example

Optimized version will be to calculate and push height up when we are checking subtrees for balanced or not. In this case, we need to return two thing to calling function, first, whether left and right subtree are balanced and second, height of corresponding left and right subtree which will be used to decide if subtree at parent is balanced or not. Since we can return only one value from function in C, we will use a pointer to catch value of height.

Please share if there is something wrong or missing,we would love to hear from you. Sharing is caring.

Find height of binary search tree

Height of binary search tree

After discussing BST and basic operations on BST, let us workout some other problems which involve some attributes of binary search tree. One such attribute is height of BST. What is Height of binary search tree or binary tree?

Height of binary search tree is maximum of distances between root and leaf nodes of tree. In other words, it’s 1 + maximum number of edges from root to any of the leaf node. For example, height of tree given below is 3.

height of binary search tree

where as height of this tree is 4.

height of binary tree

Usually, there is some confusion between depth of a node and height of tree. Depth of a node is property of a node and is distance between that node and root. However, height of tree is tree property and defined as maximum depth of any node of tree. See how they are related; height of tree = maximum depth of a node in tree. 

Calculate height of binary search tree

Height of tree is calculated bottom up, that means, we calculate height of leaf nodes first and then add that up to their parent, then parent of parent and so on till we reach root node.

Now, any node in BST can have two children. Question is whose height should we consider to add to get it’s parent’s height? As per definition, height is maximum distance of leaf node from root, hence, we should take the value which is maximum and push it up to parent.

This problem is classic case of applying divide and conquer and greedy algorithms. Divide and conquer as height of a node is decided by heights of it’s subtree, so we divide the problem till we don’t have leaf node and then solve simple problem and go up.

Greedy because at each node we select the maximum height of left or right subtree.

1. If tree is empty, return 0.
2. For each node,
   2.1 If it has left child, find height of left subtree (lheight)
   2.2 If it has right child, find height of right subtree (rheight)
   2.3 Return 1 + maximum of lheight and rheight.

Implementation is quite simple using recursion.

Example how height of tree is being calculate in algorithm

height of binary search tree example

Complexity of algorithm to find height of binary search tree is O(N) as we will visit each of node at least once.

Please share if something is wrong or missing. Sharing is caring.

Check if two binary search trees are identical

Check if two BST’s are identical

In previous posts, we discussed binary search tree and it’s properties, let us solve a problem. Problem statement is : given two binary search tree, find if two binary search trees are identical or equal? For example, below two trees are identical,

binary search trees are identical

where these two trees are not identical.

binary search trees are identical example

How to find if two BSTs are identical?

There is simple but  inefficient solution. First traverse both trees inorder and store it in arrays. Then problem reduces to check if two arrays are equal or not, which can be done in linear time.  Problem with this solution is that it use additional memory and an extra traversal.

Optimized solution is to use divide and conquer. At each node, check if values are same, then problem reduces to check if left subtrees and right subtrees of those nodes are identical. Algorithm is given below.

Algorithm to find if two binary search trees are identical

1. Start from root of both trees
2. If both trees are empty, return true
3. If one of tree is empty and other is not, then return false.
4. Check these three conditions
   4.1 check if root1->value == root2->value, if not return false
   4.2 Check if left subtree of root1 and root2 are equal
   4.3 Check if right subtree of root1 and root2 are equal
5. If all points in step 4 are true, return true else false.

Implementation to check if two binary search trees are identical is quite simple.

Complexity of algorithm to find if two binary search tree are identical or equal is O(N) where N is number of nodes in smaller tree.

Please share if something is wrong or missing, we would love to hear from you. Sharing is caring.

Inorder traversal without recursion or stack

Inorder traversal without recursion or stack

In last post Threaded binary search tree, we learned what is threaded trees and how to convert a BST to threaded tree. In this post, we will discuss, how can we use threaded BST, how to do inorder traversal without recursion or stack.  Inorder traversal of BST with recursion and stack explains how to do inorder traversal without recursion and using stack.

With threaded binary search tree, right pointer of a node either can be a genuine right child of node or it can be a thread which points to the inorder successor of the node. How can we use this information to traverse a tree?

Inorder traversal without recursion or stack

To traverse a threaded binary search tree, first go to left most node of tree. Why? Because that will be first one to print in inorder traversal. In typical recursion method, we reach to parent by function call return, and in stack based approach, we keep track of parent using stack. In threaded tree, we don’t need to keep track of parent.  At any given node, when there is no right child, it automatically redirects to inorder successor of the node.

Algorithm is something like this:

1. Go to left most node of tree, call it currentNode.
2. While currentNode is not null
   2.1  Print currentNode
   2.2  If currentNode->isThread is true
        2.2.1 Set currentNode = currentNode->right
   2.3  If currentNode->isThread is false
        2.3.1 set currentNode to left most node of currentNode->right.

Inorder traversal without recursion or stack example

Let us understand this algorithm using an example:

inorder traversal without recursion or stack

We will start with root i.e 30 and find left most node, which is 10. CurrentNode = 10. Print 10. Right pointer of 10 is thread, so follow that lead and reach at 15. Print 15.  Right pointer of 15 also is thread, so follow that and reach 20.  Print 20. Now, right pointer of 20 is not thread, so go to right node, i.e 25 and find left most node. which will be 25 itself. Print 25.  25 has right pointer as thread, so move to 30 and print it. At 30, right pointer is not thread, so move to left most pointer of tree rooted at 40. Left most node is 37. Print 37. Right pointer of 37 is thread and follow it and print 40. Right pointer of 40 is not thread, so find left most node of 47( right child of 40 ). which is 47 itself. Print 47 and now, right child is NULL and isThread is also false, so exit the loop.

Hope this walk through help you understand workflow. Let’s see some code

Complexity of inorder traversal without recursion or stack is O(N). There is no extra space required.

There is an argument that there is space requirement when converting BST to threaded BST and also for storing a boolean per node. Answer to that question is BST is converted to threaded tree only once and scanned again and again. Consider a case where multiple processes are scanning tree, if they all use extra space while scanning tree, we may use more memory than one time memory required while conversion. Same argument holds true for an extra boolean, if multiple processes use the same tree, memory used during scan is way more than one time allocated memory.

Please share if there is something wrong or missing. We would love to hear from you. Sharing is caring.

Threaded binary search tree implementation

What are threaded binary search tree?

Threaded binary search tree is BST in which all right pointers of node which point to NULL are changed and made to point to inorder successor current node (These are called as single threaded trees). In completely threaded tree (or double threaded trees), left pointer of node which points to NULL is made to point to inorder predecessor of current node if inorder predecessor exists. Refer inorder successor and predecessor to understand more on inorder predecessor and successor. Example of threaded binary search tree is as below

Threaded binary search tree
Single threaded tree
double threaded binary search tree
double threaded tree

Now, there is small thing needs to be taken care of. A right or left pointer can have now two meanings : One that it points to next real node, second it is pointing inorder successor or predecessor of node, that means it is creating a thread. To store this information, we added a bool in each node, which indicates whether pointer is real or thread.

Structure of node for threaded binary search becomes :

Why do we need Threaded binary search trees ?

First, to make use of already allocated memory, like all pointers in leaf nodes of BST is always pointing to NULL. Number of pointers used at leaf level is maximum, we can use them to connect to some real information and then use this information to optimize some operation on BST.

One example which comes to mind is inorder traversal of BST without using stack and recursion. If we have inorder successor information stored in BST using thread, this is a very simple and efficient traversal with no extra explicit or implicit space used.

How to created a threaded BST?

As mentioned earlier, node definition of tree changes a bit to figure out if the right pointer is thread or pointing to genuine right child of node.

First, let’s if we have already a tree and we want to convert it into single threaded tree. Make sure node already has boolean in it. Later, we will see how to create a threaded BST from scratch.

To convert a BST to threaded binary tree, we will first do inorder traversal of tree and store all nodes in queue. Next, we will again do inorder traversal and whichever node does not have right child link it to node at front of queue. Also, take care that node is take out of queue when it is processed. Implementation is quite simple.

Threaded binary search tree implementation

This method has couple of drawback which are worth talking about. First, each very apparently uses extra memory to store all nodes. Second, it requires two traversals of tree.

In next post, we will see how to optimize this method so as to created threaded binary search tree in single traversal and also, we will see how can we do inorder traversal of BST without using stack and recursion.

Please share if there is something is wrong or missing. Sharing is caring.

Second largest number in binary search tree

Second largest number in binary search tree

In last post : Find minimum and maximum in BST, we learned how to find minimum and maximum node in BST using recursive as well as iterative way. Today’s problem is to find second largest number in BST. Second largest number is such that there is one node which is greater than it. For example in binary search tree below, second largest number will be 40.

find second largest number in BST

Second largest number in binary search tree : Algorithm

First method is to scan through entire tree in inorder way, store it an array and then return last to one element from it. This method requires only one traversal of tree, however, uses extra space to store inorder traversal. Complexity is O(N) in time and O(N) in space.

Second method is to inorder traverse tree twice. First calculate number of nodes in tree, call it n. Now, traverse again and find (n-1)th node. This does not require any additional space, but traverses the tree twice.

One thing, we know for sure that we have to do inorder traversal of BST as it gives us sorted order of nodes and it would be easier to find second largest element in that order. In second method, our concern was that we are traversing tree twice, once to find number of nodes and then to find second largest node.

How about traversing BST inorder but in reverse order, so that it still gives  nodes sorted but in descending order. Then all we need to find is second node in that order. This requires only one traversal of tree and no extra space.

Second largest number in binary search tree : Implementation

Code below is generic code which can find any largest element in BST by setting K correctly.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;
 
void findSecondMaximum( Node * root, int *count, int K ){
	if( !root ) return;
 
	findSecondMaximum(root->right, count, K);
 
	if( ++(*count) == K ){
		printf("\n %dth element in tree : %d", K, root->value);
		return;
	}
	if( *count < K ){
		//Processing left subtree only if count is still less than K
		findSecondMaximum(root->left, count, K);
	}
} 
 
void inorderTraversal(Node * root){
	if(!root)
		return;
 
	inorderTraversal(root->left);
	printf("%d ", root->value);
	inorderTraversal(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);
	}
	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;
	//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, 38);
	root = addNode(root, 45);
	printf("\nInorder traversal of tree is : ");
	inorderTraversal(root);
	printf("\n");
	int count = 0;
	int K = 2;
	findSecondMaximum(root, &count, K);
 
	return 0;
}

Complexity of finding second largest elements still remains O(N) as in skewed binary search trees, we may have to traverse n-1 nodes.

Please share if something is wrong or missing in this post. Sharing is caring.

Minimum in binary search tree

Find minimum in binary search tree

We discussed binary search tree and it’s properties.  Properties of binary search trees are: 1. Left child node is less than its parent node. 2. Right child node is greater than its parent node. These properties hold good for all subtrees in a BST. Today, let’s discuss a problem which uses these properties of BST, and the problem is : Find minimum in binary search tree. On the same lines, it can also be asked to find maximum in a binary search tree. For example in given binary search tree, minimum is 15 and maximum is 45
find minimum in binary search tree

Both problems can be handled in similar way, only difference is the part of tree which is traversed.

As per the property of BST, all nodes on left side of a given node are smaller and all nodes on right side are greater than it. How to use this information to find minimum in binary search tree?  Minimum will have no children on left subtree of it. Why? Because, if left subtree of current node has children, they will be smaller than current node and hence it cannot be minimum. Hence, minimum will be left most node of binary search tree. While finding minimum, we never go to right child of any node in path till left most node.

Minimum in binary search tree implementation

Implementation wise, solution to find minimum in binary search tree can be implemented in iterative as well as recursive way.

Iterative method

Recursive method

Continuing on the same lines, what will be the maximum in binary search tree? It should be rightmost node in BST.

Maximum in binary search tree implementation

Iterative method

Recursive method

Complexity of algorithm to find minimum in binary search tree is O(N) in case tree is completely skewed and O(log N) in balanced binary search tree. Complexity remains same to find maximum in binary search tree.

Please share if there is something wrong or missing. If you are interested in contributing to website, please write to us.