Programming Interview Questions : Delete a Node in Binary Search Tree

Delete a node in binary search tree (BST).

Analysis

This is typical programming interview question to check candidates understanding about binary search tree property and how it can be maintained when a node is deleted from BST.

First problem is to locate node given binary search tree. Once the node is located, there are three cases to be considered before deleting node.

Case 1 :
If the given node is leaf node. Straight forward, delete the node.
For example, tree is like given below and we need to delete 4.
It would be deletion of node 4 and setting the left child of 6 as NULL.

Binary Search Tree
Fig :1 BST


BST after deleting left most node


Case 2 :
If the node is not leaf node and there is right sub tree to it. In this we would replace the deleted node by the in-order successor of the node in BST. Free the in-order successor node.
Let’s say in the above tree we need to delete 15. Node 15 has a right sub tree. We would first find the in-order successor of the node 15 and replace node 15 with that element, in this case, it is 17. And then we will free the node 17. Output will look like this.

BST after deletion of right most node


Case 3:
If the node is not leaf but does not have right sub tree, then we link the parent of the given node  with the left child of the node.
Let’s consider we need to delete 15 now. Since the node as left sub tree, we need to connect the parent of the node to the left sub tree of the node. So now node 10’s right child will be 13. Note that here we cannot replace 15 with 13 and delete 13 as 13 might have its own children.

BST


Output will be

BST after deleting non leaf node


code

Driver program for above code, change the function call to delete_node. 🙂


This execution is based on following binary search tree:


Binary search tree


Enter the number : 12
In-order before deletion : 10, 12, 20, 30, 37, 40, 45,
Since 30 is greater than 12, moving to left sub-tree
Since 20 is greater than 12, moving to left sub-tree
Since 10 is less than 12, moving to right sub-tree
 Case 1 :Deleting 12
In-order after deletion : 10, 20, 30, 37, 40, 45,

Enter the number : 20
In-order before deletion : 10, 12, 20, 30, 37, 40, 45,
Since 30 is greater than 20, moving to left sub-tree
Case 3 : Deleting 20
In-order after deletion : 10, 12, 30, 37, 40, 45,

Enter the number : 30
In-order before deletion : 10, 12, 20, 30, 37, 40, 45,
Case 2 : Deleting 37
In-order after deletion : 10, 12, 20, 37, 40, 45,

Complexity analysis

To locate any node in a BST is O(logN) given that tree is not completely skewed where the complexity becomes O(N). Once we locate the node, finding in-order successor is the costliest operation among three cases which can be done in O(logN). Hence the complexity of of overall algorithm will be O(logN).

Reference : For details how to find in-order successor of a given node in binary search tree, please refer to Inorder successor and predecessor without parent pointer.

Find Closest Element in Binary Search Tree

The problem of finding a closest element in a tree to a given value is another case where we can use the property of binary search tree.

Problem statement 

Given a Binary Search Tree and a value, find the closest element to the given value in BST.

Analysis

Simple approach is to go to all elements of BST and find out the difference between the given value and value of the element. Get the minimum value and add or subtract that minimum value from the given value, we would get the closest element in the BST.

Do we really need to scan all the nodes? No we don’t need to.

Let’s consider it case by case.

Case 1 : 
If the value of the node under consideration is equal to value, then our minimum difference would be zero and closest value would the value itself.

Case 2 :
If the value of the node under consideration is greater than given value.
By virtue of BST, we know that nodes on the right side of the given node would be greater than this. Hence the difference between the given value and all nodes on the right side would only increase. Hence there is no element on the right side, which is closer than the node itself. Hence the right sub tree is discarded.

Case 3 :
If the value of the node under consideration is less than the given value.
Again same logic applies as in case 2. Since all elements in left sub tree are less than the node, difference between given value and the nodes on left side would only increase. Hence we can safely discard the left sub tree.

Algorithm

  1. Start from the root, initialize min to MAX_INT 
  2. If the difference between the node and given value is less than minimum, update minimum.
  3. Now, check if the given value is less than the node value, search closest element in left sub tree. Here, candidate is root till now.
  4. If the given value is greater than the node value, search closest element in right sub tree. 
  5. Take care while comparing minimum value and difference and storing the minimum value. We need to store minimum value with the sign.

Code

Driver program for above code, change the function call.


Execution

This execution is for the following tree:

Enter the number: 14
Difference between node value 30 and given value 14  is :16
Difference between node value and given value is less the current min 1000 hence updating min to 16
Since node value 30 is greater than given value 14, moving to left sub tree

Difference between node value 20 and given value 14  is :6

Difference between node value and given value is less the current min 16 hence updating min to 6
Since node value 20 is greater than given value 14, moving to left sub tree

Difference between node value 10 and given value 14  is :-4

Difference between node value and given value is less the current min 6 hence updating min to 4
Since node value 10 is less than given value 14, moving to right sub tree

Difference between node value 12 and given value 14  is :-2

Difference between node value and given value is less the current min 4 hence updating min to 2
Since node value 12 is less than given value 14, moving to right sub tree

Closest Element is 12

Complexity analysis

Average complexity of this algorithm is O(logN), but if the tree is completely skewed, i.e worst case complexity would be O(N).

Binary Search Tree : Bottom up approach to problems

Delete, Mirror, Replace operations on BST

In Binary Search Tree, there is a class of problems which have solutions with similar structure.
These problems involve deletion of complete BST, mirroring a BST, replacing parent node with sum of children etc. In this post we would discuss the structure of the solution and their execution in run time in detail. Once this strategy is mastered, most of the BST problems can be solved easily.

  1. Delete a given binary search tree
  2. Mirror a binary search tree 
  3. Replace value of a node with sum of its children nodes.

Analysis

Problem 1 :Delete a Binary Search Tree

To delete a binary search tree, we start with leaf nodes. Once all leaf nodes are deleted, we move to upper layer which in turn would have become leaf nodes now. We continue to do so till the time we reach root node and then delete root node.

Algorithm

  1. Start with root node.
  2. If root is null, return.
  3. Check if there is left child, delete the sub tree with root as left child.
  4. Check if there is right child, delete the sub tree with root as right child.
  5. Delete the root node.
Video to delete a binary search tree



Code

Problem 2 : Mirror a given Binary Search Tree

To mirror a BST, we need to again start from the leaves. We first swap the lower most nodes, then move up till  the root.

Algorithm

  1. Start with root node.
  2. If root is null return
  3. If there is left child, then mirror the left sub tree.
  4. If there is right child, then mirror the right sub tree.
  5. Swap left and right child.
Video of mirror a binary search tree algorithm


Code

Problem 3 : Replace node with sum of its children

This problem requires clarification. Consider a tree as below.


Output should be as



This problem again demands that left and right tree should be solved first and then the root.

Algorithm

  1. Start with root node.
  2. If root is null return zero.
  3. If there is left child, replace the left child with sum of its children.
  4. If there is right child, replace the right child with sum of its children.
  5. Replace the root with sum of its right and left child.
Video for replacing node with sum of children


Code

If we see closely, all three codes are very similar in structure. We first put the termination condition, solve the given problem for the left sub tree, solve the given problem for right sub tree and then do the processing to update the root.

Driver program for above code, change the function call 🙂


Complexity analysis

All such kind of problems require to visit every node of the tree, hence complexity of all above problems is O(N).

Binary Search Tree : Inorder successor and predecessor without parent pointer

Find inorder successor/predecessor of given node in binary search tree

There are many applications like this where we need to find out inorder successor or predecessor of a node in binary search tree. 

What is inorder successor in binary search tree?

Inorder successor is node which will come after a node in inorder traversal of binary search tree. In other words, it would be the next larger element in BST.

There are four cases:
1. If there is a right child of the given node. In this case the smallest element in the right sub tree would be the inorder successor.
2. If node does not have right sub tree and if last turn was right, then the node where we took the last left turn will be the inorder successor.
3. If node does not have right sub tree and if last turn was left turn, parent of the node is inorder successor.
4. If the node is the right most node, then there is no inorder successor.

It is clear from the analysis that we need to change the candidate only when we are moving towards left and not when moving right.

Let’s see some examples:


In this in-order successor of 8 is 10.

 Here, in-order successor of 12 is 14.

Here in-order successor of 4 is 6.

This is special case, where the node has right sub tree, then minimum element in the right sub tree is the in-order successor. In-order successor of 14 is 15. Similarly, In-order successor of 6 would be 8.

Notice something? Yes, in-order successor of a node is the node where we took latest left turn

For 8, we took left turn at 10, for 12 we did it at 14 and for 4, we did that at 6.

Algorithm to find inorder successor

1. Start with root.
2. If the node is given has less than root, then search on left side and update successor.
3. If the node is greater than root, then search in right part, don’t update successor.
4. If we find the node and if the node has right sub tree, then the minimum node on the right sub tree of node is the in-order successor.
5. Return successor

Code

Complexity analysis

Complexity of algorithm to find inorder successor will be O(logN) in almost balanced binary tree. If tree is skewed, then we have worst case complexity of O(N).

Inorder Predecessor in binary search tree (BST)

Case 1: Node has left sub  tree.

In this case the right most node in the left sub-tree would be the inorder predecessor.

For example in above tree, in-order predecessor of 8 will be 6

Case 2: Node has no left sub-tree.

In this case in-order predecessor will be the node where we took the latest right turn.


In this example, in-order predecessor of 15 would be 14



In this example, in-order predecessor of 12 would be 10


Case 3 : Node is left most node of BST.

There is no in-order predecessor in this case and In this case there won’t  be any right turn.

In this example, in-order predecessor of 6 will be NULL.

Code

Complexity analysis

Complexity of finding inorder predecessor would be same as inorder successor i.e. O(logN).

Two numbers/nodes with given sum in binary search tree (2Sum problem)

2 Sum Problem : Find two nodes with sum in binary search tree

Given a binary search tree and an integer ‘K’, find all pairs of nodes (a,b) which have sum equal to K, i.e. a+b =K. In other words, find two nodes in binary search tree which have sum equal to a number.

This is a typical example of using binary tree property that all nodes on the left side of root are less than it and all on right are greater than it.
How can we use that? Simple idea is to find left most (minimum element in tree) and right most (maximum element in tree). Now add them up. If they add up to given number,  this is the pair.
If they don’t add up, there are two cases:
1. Sum is less then given number
In this case we need to increase the smaller number. We can do that       by getting in-order successor of minimum element. 
2. Sum is greater than given number

In this case we decrease the bigger number. We can do that by finding the in-order predecessor of bigger element.So our problem reduced to finding in-order predecessor and successor of an element in binary search tree.

Please refer to my post explaining how to find successor and predecessor of a node. I am using that code here directly.

Code to find two node with sum in binary search tree


Driver code for above function, change the function call

Execution

Let’s consider this tree:
Two nodes with given sum

Execution of algorithm for above tree would be:

Pair being considered is (2, 9)<<<Init
Pair being considered is (2, 7)<<<greater node decreased
Pair being considered is (2, 6)<<<greater node decreased
Pair is (2, 6)                <<<<<<<Pair found
Pair being considered is (3, 5) <<<<Both greater node decrease and lower node increased
Pair is (3, 5) <<<<<Found another pair.
Termination

Scanning of elements for inorder predecessor and successor will require O(logN). For every node either we will be finding predecessor or successor. Hence total complexity to find two numbers with given sum in binary search tree would be O(NlogN).

Lowest common ancestor in binary tree

Lowest common ancestor in binary tree 

Given a binary tree (not a binary search tree, refer Post for that), find the lowest common ancestor of two given nodes.

Don’t want read, watch video here 🙂


Analysis

We do not have luxury of BST property here so we need to think of something else here.
What is the condition for a node to be LCA of two nodes. Condition is that paths for both given nodes should diverge from the candidate node.Till the time we have path common for given nodes, we have common ancestor but they are not lowest. How can we find where paths are diverging? Here is how: 

Algorithm to find least common ancestor in binary tree

  1. Find any one node in the tree.
  2. Once one node is found, move up to parent and check if other resides on the other side of the parent.
  3. If other resides on other side of the parent, then parent is LCA.
  4. If it does not, continue to check parent of parent, till we have reached root.
  5. If we don’t find any such node while moving up, LCA is the node which is found in step 1.

Implementation

For every node in tree, check for if any of the given nodes in left side of the node. As soon as we encounter a node which is equals to one of the nodes given, return that node. After that, check for other node in right sub tree of the parent of returned node. If we find other  node on the right side of the parent node, then parent node is LCA.
If we found a node on left side and do not find other on the right side, then other node is below the returned node from left side, hence that node is LCA. If we don’t find any node in the left tree, then both nodes are on the right side of the node, move to right side of the node. Follow the procedure again.
Let’s take an example to see this algorithm work. we have tree as                     

lowest common ancestor
 Binary Search Tree

Find LCA of 2 and 5.For root 6, we would first move to left side and search for 2 and 5 in sub tree root at 3. Again we would search 2 and 5 in left sub tree in tree rooted at 3. In this step we would look for nodes in left sub tree of tree rooted at 2.

This time we would find 2 which is one of the two nodes. We would return node 2, let’s call it left.

Once we get this node we would look on the right side of sub tree of the tree rooted at 3.

Once again, we would hit one of nodes we are looking for i.e. We would return 5.let’s call it right.

Now at node 3 we have both left and right as non-null, hence 3 is the lowest common ancestor.

Tip: We don’t need to look into the left and right tree of the node which is equal to one of nodes we are searching for, as in any case that would be the LCA if we don’t fins other node in right sub tree of parent . (Think loud!).We only need to look into the right part of the parent of the node, if the other node is on the right side of the parent, then this node cannot be LCA, but the parent is the LCA.

If we don’t find other node once we find one, we assume that the found node is the LCA, as other node can be below that node.

Consider another example, find LCA of 2 and 3.
1. We look on the left sub tree of tree rooted at 6.
2. We go to 3. 3 is the node we are looking for. return from here.
3. Check for the other node in right sub tree of parent node i.e 6.
4.  We would not find any of the nodes 2 or 3 on the right side of 6.
5. Hence we return node 3 as LCA.
So there is a problem here, what if there is only one node present in tree. we would report that node as LCA.

Code

Complexity analysis

We would be scanning all nodes at once for comparison with the given nodes, hence worst complexity of finding lowest common ancestor in binary tree will be O(N).

Lowest common ancestor in binary search tree

Find Lowest common ancestor  (LCA)


A problem which uses the property of Binary Search Tree (BST) is finding Lowest Common Ancestor commonly know as LCA.

Given two nodes, find the lowest node which is parent of both given nodes, that is least common ancestor (LCA). For example in following tree, LCA of 2 and 5 is 3.
Least common ancestor

If you don’t want to read, watch video instead.


Algorithm

As we know BST has a property that all nodes on left side of a node are less than node and on right side are greater than the node. Can we use that property to solve this problem? 

Lowest common ancestor of two nodes will be the node when path of two node diverge, i.e. one node is greater than node under consideration and other is greater. What are the other cases?

Case one : 

Both given nodes are less than the node under consideration
In this case, LCA is on the left side of the node, hence we look for one on the left side of the node.

Case two: 

Both given nodes are greater than the node under consideration
In this case, LCA is on the right side of the node, hence we look for one on the right side of the node.

Case three: 

One of the two nodes is parent of other.
In this case LCA is parent node.

Code for find least common ancestor

Driver program for above function, change the function call 🙂

Complexity analysis

As we can see we are reducing our candidates by half every time we do the comparison and in worst case we would make comparisons equal to depth of the tree. Depth of a tree, given tree is not completely skewed, is roughly logN, hence complexity of this algorithm is logN. If the tree is completely skewed and there is parent child relationship between given nodes, then we need to compare N nodes and our complexity becomes O(N) in worst case.