Remove particular combination of characters

Remove particular combination of characters from string.

Given a string, we need to remove a particular combination of characters, for example, if s = “aacbbdccaac” and if combination is “ac” then our output will be “abbdcca”. If s = “aacaaccd” and if combination is “ac”, then output should be “acd”. Following will be the execution  aacaaccd ——-> aacd ——>ad 
Note that this has to be done in linear time and without any extra space.

Here there are two subparts of the problem: One, we need to keep track we have already encountered the first character in the combination of characters needed to be removed.
Second we need to keep track of the position where the next character should be placed in the string if it is not to be eliminated. First problem can be easily solved by maintaining a state machine, where we have two states and one moves from one state to another based on the input. In current example, we have states like state “INITIAL” and “MOVED”, Whenever we encountered “a”, we move from INITIAL to MOVED. Then if we get “c” in “MOVED” state we are sure that we have encountered the whole pattern and they need to be removed. If we are in “MOVED” state and if we don’t get “c”, we move back to “INITIAL” state.

For the second part, we can simply follow the approach we have used in this post, that is to maintain two pointers, one to point to the character to be processed, and other to point position where current character to be placed if it is not be eliminated.
The problem can be extended with multiple characters in pattern, with change in state machine accordingly.Same state machine method can be used to count number of words in a given string. Whenever we encounter the separator, we move to OUT state and as soon as we see first character in OUT state we move to IN state till we again see separator.

#define INITIAL 1
#define MOVED 2
char * remove_pattern(char *s, char * pattern){
    int state = INITIAL;
    if(s == NULL) return NULL;
    if(pattern == NULL) return s;

    char * source = s;
    char * destination  = s;
    while(*source != ''){

        /*If character is not equal to the first character of the pattern,
          copy it as such */
          if(state == INITIAL && *source != *pattern){
               *destination = *source;
               destination++;
          }
          else if( *source == *pattern && state == INITIAL){
              /* Move state to MOVED */
              state = MOVED;
          }else if(state == MOVED && *source != *(pattern + 1)){
                /* If next character is not as per pattern, 
                   copy previous character first. */
                *destination =  *pattern;
                destination++;
                /* If next character is first character of the pattern,
                   move state to INITIAL */
                   if(*source != *pattern){
                       *destination  = *source;
                       destination++;
                       state =  INITIAL;
                   }
             }
         /* If we hit the pattern, start again and move state to INITIAL */
          else if(state == MOVED && *source == *(pattern + 1)){
                state = INITIAL;
          }
          /* After moving the characters, check if they 
            don't make pattern again */
          if((int)(destination-s) >= 2
              && *(destination -2) == *pattern
              && *(destination-1) == *(pattern +1)){
              destination -=2;
          }
          source++;
    }
    *destination = '';
    return s;
}

Test cases
1. When pattern is present
s= “aaacacacbbb” pattern = “ac”

2. When pattern is not pattern
s =”aaaabdcaaa” pattern  = “ac”
3. When movement leads to pattern again
s= “abacaccdc” pattern =”ac”

4. When string is NULL or pattern is NULL s= NULL pattern = NULL
5. When return string is empty s = “acacacac” pattern =”ac”

6. Just first character in pattern s= “aaaaaaaaa” pattern =”ac”

The complexity of the above code is O(N) and no extra space used.

Loop in linked list

Loop in linked list

Detect loop in linked list is very common linked list question which is asked in telephonic interview rounds. Problem statement is :

Given singly linked list, check if there is loop in linked list and if yes, find start node or point of the loop.

For example, if for linked list shown below, there is a loop in linked list and it start at node 8.

loop in linked list
Loop in linked list, starting node is 8

Loop in linked list : thoughts

What is difference between a normal singly linked list and a linked list with loop? If we traverse normal linked list, we are destined to encounter a node which is null, which in effect is the last node of normal linked list. However, in a linked list with a loop, we will never reach null and circle around in the loop.

Can we use this property to find if there is a loop or not in a linked list? If we move two pointers with different speeds,, the fast pointer, which moves two nodes at a time will reach to end of linked list before slow pointer, which moves one node at a time, in a normal list (without a loop). However, in list with loop, fast pointer will go around in circles and eventually, slow pointer will catch up with it. So, if ever, before fast pointer reaches null, slow pointer catches up with it, there is definitely a loop in linked list. This method of using fast and slow pointers to traverse linked list at different speeds is commonly known as hare and tortoise method and used in solving many problems on linked list like find middle of linked list, palindrome linked list etc.

Let’s take an example and see what we are thinking is correct. Below is a linked list with a loop, let’s see if slow and faster pointer ever meet.

We initialize slow as head(4) and fast as next of head(3).  fast moves two steps and hence reaches node 8, where as slow reaches at 3.

Since, fast is not null yet, we jump again, this time fast points to 7 and slow points to 5.

Again, fast is still not null, so we move again, fast now is at 8 and so is slow.

This is where we can safely say that there is a loop linked list.

    public boolean isLoop(){
        /* 
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return false;
        }
        
        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here
        
        while(fast != null && fast != slow){
            /*
            Move faster ponter two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return false;
            
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }
        
        return fast == slow;
    }

There is common mistake which happens is to check content of fast and slow pointers to see if there are at the same node. This will fail when there are duplicate values in different nodes. To avoid wrongly predicting nodes being equal when actually content is equal, compare node addresses and not content.

Start of loop in linked list

This problem is interesting and require a bit of thinking. Can we find number of nodes in loop?
Starting from node fast and slow met at, move fast two nodes at a time and slow one node at a time, they will again meet at the same node. Keep count of how many nodes slow pointer moved, it will give length of loop. You can try with different length loops and see that it is actually true.

private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

Now, we have number of nodes in loop, let’s say k. How can we find starting node of loop. We take two pointers again, fast and slow, fast is k nodes ahead of slow which is at head of list. Why? Hypothesis is that if we move them with same speed, when slow reaches start of loop, fast would have finished traversing k loop nodes and will also be at the start of loop. So, with fast ahead of slow by k nodes, when both meet, that node should be start of loop in linked list.

Start of loop in linked list implementation

package com.company;

/**
 * Created by sangar on 14.10.18.
 */
public class LinkedList<T> {
    private Node<T> head;

    public LinkedList(){
        head = null;
    }

    public void insert(T data){
        //If this is the first node to insert
        if(this.head == null){
            this.head = new Node<>(data);
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier,
			it should not be null in this while loop ever though
            * */
            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            //We are at the last node.
            current.setNext(new Node(data));
        }
    }

    public Node getLastNode(){

        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;

            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            return current;
        }
    }

    public Node<T> get(T data){
        /*
            Base condition if there is no nodes,
            return null
         */
        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier, it
			should not be null in this while loop ever though
            * */
            while(current != null && current.getData() != data){
                current = current.getNext();
            }

            return current;
        }
    }

    /* As we need slow pointer to get number
    of nodes again, we will return slow pointer
    rather than boolean
     */
    private Node isLoop(){
        /*
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return null;
        }

        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here

        while(fast != null && fast != slow){
            /*
            Move faster pointer two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return null;

            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }

        return fast == slow ? slow : null;
    }

    private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

    public Node getStartNodeLoop(){

        Node slow = isLoop();

        /* If slow is not null, it means there is a loop */
        if(slow != null){
            int k = getNumNodesInLoop(slow);

            slow = this.head;

            //Give fast head start of k nodes.
            Node fast = slow;
            while(k-- > 0 && fast != null){
                fast = fast.getNext();
            }

            while(fast != slow){
                slow = slow.getNext();
                fast = fast.getNext();
            }
        }
        return slow;
    }
}

Test cases for finding loop in linked list implementation

package test;

import com.company.LinkedList;
import com.company.Node;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class LoopInLinkedListTest {

    LinkedList<Integer> tester = new LinkedList<>();
    @Test
    public void loopPresentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        //Created a loop
        Node loopNode = tester.get(8);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopAbsentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void EmptyLinkedListTest() {
        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void OneNodeLoopTest() {
        tester.insert(4);

        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopBackToHeadTest() {
        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(5);
        tester.insert(7);


        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }
}

Complexity to find a loop in linked list is O(n) as we have to scan all node of linked list at least once.

Please share if there is something wrong or missing.

Reference : cslibrary.stanford.edu/103/LinkedListBasics.pdf

Merge two sorted linked lists

Problem statement is simple: Merge two sorted linked lists, without using extra space. To refer to the basics of linked list, please follow the post : Linked list data structure. This problem is commonly asked in a telephonic round of Amazon and Microsoft. Let’s take an example and understand what is required as a solution. Given two linked lists as following,

merge two sorted linked lists
Two sorted linked lists

Result should be like this:

merge two sorted lists
Resultant linked list.

Consider the following two steps to merge sorted linked lists. First, figure out which node should be head of result list. Compare head nodes of two give lists, whichever is smaller, that should be the head of result list.

Second, compare two nodes, one from each list and decide which should go next in result linked list.  Advance the pointer to next node of the node which is added to result list.

As no new node is allocated during this merge, we have to make sure that all the references are maintained when nodes are added to merged linked list.

merge two sorted linked list
Two sorted list to be merged

We can start with one list as merge list and add nodes from second list at appropriate place in that list. Let’s say L1 is our merged list and we always compare node on L2 to see if it should be placed in L1 at current position. L1 grows as more nodes are sorted in merge list.

We compare first two nodes L1 and L2, and decide that node(2) has to go in merged list as head. If it was head of L2, we would have swapped L1 and L2 heads and still L1 will be head of merged list. Why? Because we want that L1 always points to last node in merged list and L1 to represent sorted merged list till this point and L2 switches between two input lists.

As L1 always points to the last node of merged linked list, next node to compare should be L1.next i.e node(4) and L2 i.e node(3).

As L1 follows the merged linked list, we will move L1.next to point node(3), however doing it directly will lead to lose of entire linked list following it. So we do it in four steps : store L1 next as temp; link L2 to L1.next; L2 points to temp and then move L1 to L1.next

Node temp = L1.next;
L1.next = L2;
L2 = temp;
L1 = L1.next
merge two sorted linked lists

Next nodes to be compared are node(5), which is L1.next and node(5) which is L2.

Comparing node 4 and 5 to add in sorted merge list

Of course node(4) has to be added to merged linked list, what should we do? First save L1.next in temp, temp now points to node(5). Second, point L1.next to L2, point L2 to temp, and at last, L1 moves to L1.next. State of two sorted linked lists looks as follows.

merge two sorted linked lists

By this time you must have noticed that L1 and L2 do not point to the one list all the time, L1 always points to the last node of merged list and L2 points to first node of separated list which needs to be merged.

Now, L1.next which is node(7) and L2 which is node(5) will be compared.

node(5) is to be added in merged sorted list. Again same set of steps. L1.next stored as temp, L1.next points to L2 i.e. node(5) and then L2 points to temp i.e. node(7)

merge two sorted linked lists

Again, node(9) which is L1.next will be compared to L2 i.e node(7). L1.next should point to L2. Final state will be as follows

At this point, L1.next i.e node(8) is less than L2, this is simple case, where we just move L1 to L1.next and L2 remains as is.

merge two sorted linked lists

Next two nodes follow the same pattern and added to merged sorted linked list.

merge 2 sorted linked lists
merge two linked list

At this point, special condition occurs which is L1.next is null. In this case, point L1.next to L2 and two linked lists are merged.

Two sorted linked lists are merged into a sorted list

Merge 2 sorted linked lists : Implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }

    printf("NULL");
    printf("\n");
}
Node * MergeLists(Node *list1, Node *list2) {
  if (!list1) return list2;
  if (!list2) return list1;

  Node *head;
	//Chosing head of merged list
  if (list1->data < list2->data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
	
  while(list1->next && list2) {
    if (list1->next->data > list2->data) {
	//Step 1. Save the next pointer
      Node *tmp = list1->next;
	//Step 2. Change next pointer to point L2
      list1->next = list2;
	//Step 3. Move L2 to temp
      list2 = tmp;
    }
	//Step 4. Move L1 ahead
    list1 = list1->next;
  } 
  if (!list1->next) list1->next = list2;
  return head;
}
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
	
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
 
        L1 = MergeLists(L1,L2); 
        printList(L1);
 
        return 0;
}

Complexity of this method to merge two sorted lists into one is O(n+m) where n and m are number of nodes in two sorted linked lists.

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * mergeSort(Node *a, Node *b){
    Node *result = NULL;
    if(a ==  NULL)
        return b;
    else if(b == NULL)
        return a;

    /* For the first node, we would set the result to either a or b */
      if(a->data <= b->data){
         result = a;
        /* Result's next will point to smaller one in lists 
           starting at a->next  and b */
         result->next = mergeSort(a->next,b);
      }
      else {
        result = b;
       /*Result's next will point to smaller one in lists 
         starting at a and b->next */
        result->next = mergeSort(a,b->next);
      }
      return result;
}

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }

    printf("NULL");
    printf("\n");
}

/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
      
        L1 = mergeSort(L1,L2); 
        printList(L1);
        
        return 0;
}

Please share if there is something wrong or missing. If you want to take personalized coaching from our expert teachers, please signup for free demo class.

Add two numbers represented by linked lists

Add two numbers represented by linked lists

Given two linked lists, where linked list represents a big number and each node of linked list contains one digit of the number. Problem is to add two numbers represented by linked lists. The result should be stored in a third linked list. It should be noted that the head node contains the most significant digit of the numbers.

For example. let’s say we have been given two numbers: 12563 and 56743 and we have to add them. Two linked lists which will represent these numbers are as shown below.

add two numbers represented by linked lists
add two numbers represented by linked lists

Result of adding these two linked list would be:

result of adding two numbers represented by linked lists

Adding two linked lists: thoughts

This problem is very easy to solve if the order of the digits stored in the linked list is reversed. Look at the code given at leetcode.

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       int carry =0;
 
        ListNode newHead = new ListNode(0);
        ListNode p1 = l1, p2 = l2, p3=newHead;
 
        while(p1 != null || p2 != null){
            if(p1 != null){
                carry += p1.val;
                p1 = p1.next;
            }
 
            if(p2 != null){
                carry += p2.val;
                p2 = p2.next;
            }
 
            p3.next = new ListNode(carry%10);
            p3 = p3.next;
            carry /= 10;
        }
 
        if(carry==1) 
            p3.next=new ListNode(1);
 
        return newHead.next;
    }

However, linked lists are not stored in reversed order and basic mathematics tells us that addition starts from the least significant digit. To access least significant digit of the numbers, we will visit the last nodes of both the lists and add them up, create a new node to store the result, take care of the “carry” if any.

Next, we go to the second to last node and do the same. Link the result node to the result node which was created when we added the last nodes.

This will continue  backwards till we reach head of one the list. Once, we reach head of a linked list, we just add all the nodes of the remaining list to the result.

It is clear that we go to the end of the lists and move back one node at a time. Actually, this is a reverse traversal of a linked list, which can easily be done with recursion, function call stack will automatically store previous nodes. However, we need to take into account the difference in the number of digits in two number and hence the difference in length of the two lists.

So before starting recursion, calculate the size difference and move the longer list pointer to appropriate place so that we reach the last node of both lists at the same time.

Another thing is to take care of is carry. If two digits add more than 10, forward the carry to the next node and add it to it. If most significant digit addition results in a carry, create an extra node to store carry.

Add two numbers represented by linked lists: implementation

#include<stdlib.h>
#include<stdio.h>

typedef struct node{
	int data;
	struct node *next;
} Node;


int length( Node * head ){
	int len = 0;
	Node * current  = head;
	while(current){
		len++;
		current = current->next;
	}
	return len;
}

Node * createNode(int value){
	
	Node * newNode = (Node *)malloc(sizeof(Node));
	newNode->data = value;
	newNode->next = NULL;
	
	return newNode;

}
/* Addition of a node to linked list */
void push(Node **head, int value){
	
	Node *newNode = createNode (value);
	if(!(*head) ){
		*head = newNode;
	}
	else{
		newNode->next = (*head);
		*head = newNode;
	}
}
/* This function is actually helper function 
	which does all house keeping like calculating 
	lengths of lists,calling recursive implementation,
	creating extra node for carry in MSD,
	and adding any remaining nodes left in longer list. */

/* result is pointer to pointer to the head of resulting node */ 
void addTwoNumbers(Node *L1, Node *L2, int *carry, Node  **result)
{
	int len1 = length( L1 );
	int len2 = length( L2 );
	int diff = 0;
	
	if(len1 < len2){
		Node * current = L1;
		L1 = L2;
		L2 = current;
    }
    diff = abs(len1-len2);
    Node * current = L1;
    
    while(diff--)
    	current = current->next;
    	
    /* Call the recursive implementation */
    addListRecursively(current, L2, carry, result);
    
    diff = abs(len1-len2);
    
    /* Add remaining nodes in longer list */
    addRemainingDigits(L1, carry, result, diff);
    
    if(*carry){
    	push(result, *carry);
    }
    return;
}
void addListRecursively(Node *L1, Node *L2, 
						int *carry, Node **result){

        int sum;
        if(!L1)
            return;

        addListRecursively(L1->next, L2->next, carry, result);

        /*We have reached the last node of both lists, add them */
        sum = L1->data + L2->data + (*carry);
       
        int value = sum%10;
		*carry = sum/10;
        push(result, value);
       
        return;
}
void addRemainingDigits(Node *L1, int *carry,
						Node **result, int diff){
	int sum =0;
	
	if(!L1 || !diff)
		return;
	addRemainingDigits(L1->next, carry, result, diff-1);
	
	sum = L1->data + (*carry);
	int value = sum%10;
	*carry = sum/10;
    
    push(result, value);
    
    return;
}

void printList( Node * head ){
	Node * current = head;
	while(current){
		printf("%d ->", current->data);
		current = current->next;
	}
	printf("NULL");
}
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,3);
        push(&L1,4);
        push(&L1,6);
        push(&L1,7);
        /* creating list 2 */
        push(&L2,8);
        push(&L2,9);
        push(&L2,7);
      
        printList(L1);
        printf("\n");
        printList(L2);
        
        addTwoNumbers(L1,L2, &carry, &result);
        printf("\n");
        printList(result);
        return 0;
}

Since we traverse the number of nodes in the long list, the complexity of the algorithm would be O(n), where n is the number of nodes in the long list. Also, we need n extra nodes to store the result. Hence space complexity to add two numbers represented by linked lists is O(n).

Please share if there something wrong or missing. If you are preparing for an interview, please signup for free interview preparation kit.

Binary tree to doubly linked list conversion

Binary tree to doubly linked list conversion

This is very commonly asked problem in Amazon and Google interview question. It checks your understanding of binary tree and doubly link list data structures, their traversals and creation. In a binary tree, a node has two pointers, one point to the left child of the node and other points to the right child of the node. Similarly, in a doubly linked list, a node contains two pointers, one point to the next node and other points to the previous node of the current node. Given a binary tree, how can we convert the binary tree to a doubly linked list? To make the problem clear, let’s take an example.

convert binary tree to dll
Binary tree to doubly linked list conversion

Output should be

convert binary tree to doubly linked list
Doubly linked list from binary tree

Binary tree to a doubly linked list: Line of thought

The first question you should be asking is which node should be the head of the doubly linked list? If the leftmost node in the binary tree is to be head, you need to traverse a tree in inorder. However, if the root node has to be the head node, then you should do preorder traversal.

This question could be great started as it shows your understanding of tree traversals.

Let’s say our problem is to have inorder traversal. If a binary tree is binary search tree, the interviewer can just tell you to provide the output as a sorted list, which is another way of saying inorder traversal.

To convert a binary tree to a doubly linked list, at each node, the previous pointer will point to the inorder predecessor of the node whereas next pointer points to inorder successor of the node. We have left and right pointers already in the node, use them as previous and next pointer respectively.
Now, problem is to keep track of inorder successor and predecessor of the node. To keep track of inorder predecessor, store the previous node of the current node visited throughout traversal. We would link the left child to the inorder predecessor.
How to keep find the inorder successor of a node, if the node is left child of some node, the inorder successor would be parent node. At the parent node, it would be the leftmost child of the right child if it exists. This is not scary as it sound, inorder successor part is automatically implemented if we do the recursive inorder traversal of the tree.

There is one special case to handle, which is the leftmost node. This node will be head of the doubly linked list and there is no previous node to link it’s left to. 

This whole problem is a complex version of inorder traversal of a binary tree, but at the end, it is inorder traversal. We can first write the generic inorder traversal and then modify the process step to suit our needs.

    private void inorder(Node root){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        process(root);
        if(root.right != null) inorder(root.right);
    }

We have to modify this to send previous node, where root connects it’s left child in process step and head, which is set only once, to store the head of result doubly linked list.

private void inorder(Node root, Node prev, Node head){
        if(root == null) return;

        if(root.left != null) inorder(root.left);
        process(root, prev,head);
        if(root.right != null) inorder(root.right);
    }

What we have to do in process step? If the current node is the leftmost node, we will set that head of the doubly linked list. If the previous node is null yet, that means, we have it the leftmost node.
What if the previous node is not null, in that case, we have already created or assigned head of the doubly linked list, and the previous node points to the last node of the doubly linked list. It means we have to link right pointer of the previous node to the current node.
Set left pointer of the current node to the previous node irrespective of the previous node. The last step would update the previous with the current node.

private void process(TreeNode root, TreeNode prev, TreeNode head){
	if(prev == null){
		head = root;
	}
	else{
		prev.setRight(root);
	}
	root.setLeft(prev);
	prev = root;
}

The only problem is that if we are implementing the process function Java, we cannot change the value of pointer because Java passes arguments as pass-by-value rather than pass-by-reference. In short, even though head and previous pointers are updated in process function, the change would not be reflected in the calling function. To handle this, we will create a mutable static class with two members called head and previous and pass it to process function. Why this method works, please refer  :  pass-by-value and pass-by-reference in java

    private void process(TreeNode root, Context context){
        if(context.prev == null){
            context.head = root;
        }
        else{
            context.prev.setRight(root);
        }

        root.setLeft(context.prev);
        context.prev = root;
    }

An algorithm to convert a binary tree to a doubly linked list

  1. Start from root node, currentNode.
  2. If currentNode->left != NULL, currentNode = currentNode->left. (Moving down the tree on the left side)
  3. At this point we are at the left most node, check if previous == NULL.
    1. If previous is NULL, then this node has to be the head node.
    2. Mark currentNode as head and currentNode->left = previous = NULL.
  4. previous = currentNode.
  5. Traverse up the tree in inorder traversal.
    1. previous->right = currentNode.
    2. currentNode->left = previous
    3. previous = currentNode
  6. If currentNode->right != NULL, currentNode = currentNode->right and go to step 2.

Convert Tree to DLL : implementation in Java

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeToDLL {

    public static class Context {
        public TreeNode head;
        public TreeNode prev;
    }
    
    private void process(TreeNode root, Context context){
        if(context.prev == null){
            context.head = root;
        }
        else{
            context.prev.setRight(root);
        }

        root.setLeft(context.prev);
        context.prev = root;
    }

    public void treeToDllRecursion(TreeNode root, Context context){

        if(root == null) return;

        if(root.getLeft() != null) {
            treeToDllRecursion(root.getLeft(),context);
        }

        process(root,context);

        if(root.getRight() != null)
			treeToDllRecursion(root.getRight(), context);
    }
}

Definition of TreeNode and BinarySearchTree is given below.

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

    public void setRight(TreeNode node){
        this.right = node;
    }

    public void setLeft(TreeNode node){
        this.left = node;
    }
}
package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree<T> {

    private TreeNode<T> root;

    public void BinarySearchTree(){
        root = null;
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private TreeNode insertNode(TreeNode root, int value){
        if(root == null){
            //if this node is root of tree
            root = new TreeNode(value);
        }
        else{
            if((int)root.getValue() > value){
                /*If root is greater than value,
				node should be added to left subtree */
                root.setLeft(insertNode(root.getLeft(), value));
            }
            else{
                /*If root is less than value,
				node should be added to right subtree */
                root.setRight(insertNode(root.getRight(), value));
            }
        }
        return root;
    }
    
    public TreeNode getRoot(){
        return this.root;
    }

    public void setRoot(TreeNode node){
        this.root = node;
    }
  }

Binary search tree to DLL conversion : C 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 treetoListRec(Node * node, Node ** prev, Node **ptrToHead){
        if(node == NULL)
                return;
        /* Go to left most child */
        if(node->left)
                treetoListRec(node->left, prev, ptrToHead);

        /* If this wasn't the first node being added to list*/  
        if(*prev!= NULL){
                (*prev)->right = node;
        }
        else{
                 *ptrToHead = node; 
         }
        /*make left pointer point to last node, and update the 
          last node to current*/

        node->left = *prev;
        *prev= node;

        /* If there is right child, process right child */
        if(node->right)
                treetoListRec(node->right, prev, ptrToHead);

}
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 create_node(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 * prev = 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);
        
        treetoListRec(root,&prev, &ptrToHead);
        
        return 0;
}

This requires traversal of each node at least once, hence complexity analysis is O(N).

Note

There is one method , which takes into consideration that the whole problem can be divided into sub-problems involving left sub tree and right sub tree, once these sub problems are solved, we can combine solutions of these to come up with the solution of the bigger problem.

Basic idea is to convert left sub binary tree to doubly linked list, then convert right sub binary tree to doubly linked list and join both the lists with root in between. Idea is very well explained here

Please share if there is something missing or wrong. If you want to contribute to website, please reach out to us on [email protected]

Level order traversal of binary tree

Level order traversal of a binary tree

Given a binary tree, print all the nodes of binary tree level-wise, this is another way of saying perform a breadth-first traversal of the binary tree and known as level order traversal of a binary tree. What is level order traversal of a binary tree? It means that nodes at a given level are printed before all the levels below it. For example, level order traversal of below tree would be [10,7,15,8,9,18,19]

Level order traversal of binary tree

Level order traversal: Thoughts

In a binary tree, each node has two children, when we process a node, we can already know what is at the next level. As the leftmost child at a given level has to be printed first, followed by its right sibling then by its cousins. If we store all the nodes at the next level from left to right, which data structure is best for this use case? It’s First In First Out pattern, hence the queue. Let’s see how it works with an example.

level order traversal of binary tree
level order traversal of binary tree

Start with root node and enqueue the root node in the queue.

breadth first traversal of binary tree
Root added to the queue

Now, while the queue is not empty,  dequeue node from the queue and push it’s left and right children onto queue if they exist. In this case, we will dequeue node(10) from the queue and enqueue node(7) and node(15) to queue. Output till now is 10.

level order traversal of binary tree
add next level to queue, output is 10.

Again, dequeue from the queue, node(7) and store it in output. At the same time, store it’s left child node(8) and right child node(9) to queue. The output is [10, 7]

Node(7) is dequeue and node(8) and node(9) enqueued

Now, dequeue node(15) from the queue, put it on to output and enqueue it’s left child node(18) and right child node(19) on to the queue. The output is [10,7,15].

Again, node(8) is dequeue from the queue and put on to the output, as there are no left and right child of node(8), nothing is enqueued in the queue. Same is true for all the nodes in the queue. We continue till queue is empty. Final output will be [10,7,15,8,9,,18,19].

Level order traversal of binary tree : implementation

    public ArrayList<Integer> levelOrderTraversal(TreeNode root){

        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<Integer> traversal = new ArrayList<>();

        if(root == null) return traversal;

        queue.add(root);

        while (!queue.isEmpty()){
            TreeNode current = queue.poll();
            traversal.add((int)current.getValue());
		
            if(current.getLeft()!= null)
				queue.add(current.getLeft());
            if(current.getRight()!= null)
				queue.add(current.getRight());
        }
        return traversal;
    }

As each node of the binary tree is visited at least once, time complexity  O(n) along with space complexity of O(2(l-1)) where l is the number of levels in the binary tree.

The method explained above has an additional space complexity, is there a way to avoid that?  To print all the nodes on a particular level, first of all, we must know the number of levels in the binary tree, which is nothing but the height of the tree.

Start with level 0 and print all nodes on level 0, then move to level 1 and print all the nodes at level. To reach cousins of a node, we have to come back to the parent of the parent node of the current node. How about we always start at the root node with the desired level to be printed? If the node is at the desired level, print it and start again from the root.

Implementation wise it’s simple recursive function, where we pass the desired level to be printed, at each recursive call, the desired level decreases by 1. When the desired level is 1, print the node as that node will be at the level we are printing currently.

  • Find the height of the tree.
  • For each level:
    • Start from the root for each level.
    • Decrement the level count while moving to the left and right child.
    • If the level count is 1, print the node.
    • Else move down to left subtree and right subtree.

This algorithm is more useful when you have to print a specific level of binary tree and not all. Complexity of this method to do  level order traversal of binary tree is O(n log n). 

Level order traversal: recursive implementation

    public ArrayList<Integer>
	levelOrderTraversalRecursive(BinarySearchTree tree){
        ArrayList<Integer>traversal = new ArrayList<>();

        int height = tree.height();
        
        for(int i=1; i>=height; i++){
            traverseLevel(tree.getRoot(), i, traversal);
        }
        return traversal;
    }

    private void traverseLevel(TreeNode root, int level,
								ArrayList<Integer> levelTraversal){
        if(level == 1){
            levelTraversal.add((int) root.getValue());
        }

        if(root.getLeft() != null)
			traverseLevel(root.getLeft(), level-1, levelTraversal);
        if(root.getRight() != null)
			traverseLevel(root.getRight(), level-1,levelTraversal);
    }

Definition of binary tree and tree node is as follows.

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree<T> {

    private TreeNode<T> root;

    public void BinarySearchTree(){
        root = null;
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }
    private TreeNode insertNode(TreeNode root, int value){
        if(root == null){
            //if this node is root of tree
            root = new TreeNode(value);
        }
        else{
            if((int)root.getValue() > value){
             /* If root is greater than value, 
				node should be added to left subtree */
                root.setLeft(insertNode(root.getLeft(), value));
            }
            else{
                /* If root is less than value, 
				node should be added to right subtree */
                root.setRight(insertNode(root.getRight(), value));
            }
        }
        return root;
    }

    public TreeNode getRoot(){
        return this.root;
    }

    public void setRoot(TreeNode node){
        this.root = node;
    }

    public int height(){
        return height(this.getRoot());
    }

    private int height(TreeNode currentNode){
        if(currentNode == null) return 0;

        int lh = height(currentNode.getLeft());
        int rh = height(currentNode.getRight());

        return 1 + Integer.max(lh, rh);
    }
}
package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

    public void setRight(TreeNode node){
        this.right = node;
    }

    public void setLeft(TreeNode node){
        this.left = node;
    }
}

Please share if there is something wrong or missing. If you want to take personalized coaching from our expert teachers, please signup for a free session.

Paths in Binary Search Tree

Print paths in binary search tree

Print paths in binary search tree from root to leaf node. There can be many paths in a tree. AT every node, there are two paths splitting. Maximum length of path in binary search tree can be N nodes. Consider following tree:

paths in binary search tree

Paths in given binary search tree are : [ 10,5,1 ], [10,5,6 ], [10,19,17 ], [10,19,20]

Paths in binary search tree : Algorithm

As every path start with root node, it’s obvious that first node in every path with root node.  At root node, we have two choices. We can go to left subtree or can go to right subtree. It does not matter what subtree we go first as we have to traverse all paths anyway.

Let’s say we traverse left subtree first. At this point, we have first node in path, all we need to find all paths in left subtree and append those path with first node we have.
At first left child, problem remains the same, find paths in binary search tree. Additional step is to append to existing path we have already have covered. Are you getting a hint on recursive nature of problem?

Once, we have traversed all paths on left subtree, it’s time to traverse all paths on right subtree.

To keep track of nodes which are already added to path, we have to maintain a list of nodes, which will be updated whenever we move up and down in BST.

As mentioned, path ends on leaf node, as soon as we hit a node which has no left or right child, start going back up in the tree. In implementation terms, this will be termination condition for recursive function. Algorithm to print paths in binary tree.

Paths in binary search tree : Implementation

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

typedef struct node Node;

void printPaths(Node * node, int path[], int pathLen){
	
  	int i;
	
	if(!node)
		return;
	
	path[pathLen]  = node->value;
	
	int isLeaf = ! ( node->left || node->right ) ;
	if(isLeaf ){
		printf("\n Path till node %d is :", node->value);
		for(i=0; i<=pathLen; i++){
			printf("%d, ", path[i]);
		}
	}

	printPaths(node->left,  path, pathLen+1);
	printPaths(node->right, path, pathLen+1);
	
	return ;
}

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 == NULL){
      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;
  int n = 0;
  //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 path[100];
  printPaths(root, path, 0);
  
  return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }

    public void printPath(){
        ArrayList<Node> path  = new ArrayList<>();
        this.printPathRecursive(this.root, path);
    }

    private void printPathRecursive(Node root, ArrayList<Node> path){
        if(root == null) return;
        path.add(root);

        //If node is leaf node
        if(root.left == null && root.right == null){
            path.forEach(node -> System.out.print(" " + node.value));
            path.remove(path.size()-1);
            System.out.println();
            return;
        }

        printPathRecursive(root.left,path);
        printPathRecursive(root.right, path);

        path.remove(path.size()-1);

    }
}

Test class

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();

        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);

        binarySearchTree.printPath();
    }
}

Since we are traversing each node at least once, complexity of  implementation for print all paths in binary search tree is  O(n) where n is number of nodes.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across world, please reach out to us at [email protected]

Check if tree is BST or not

This is one of the most asked programming interview questions. How to check or validate that a given binary tree is BST or not or if a given tree is a binary search tree? For example, the first and second binary trees are BST but not the third one.

binary tree is BST or not
binary tree is BST

binary tree is BST or not
binary tree is BST

binary tree is bst or not
binary tree is not BST

In binary tree introduction  we touched upon the topic of recursive structure of binary search tree.  The first property to satisfy to be qualified as BST is: value in all nodes on the left subtree of the root node are smaller and the value of all nodes in the right subtree is greater than the root node. This property should be valid at all nodes.

Check if binary tree is (BST) or not: Recursive implementation

So, to see if the binary tree rooted a particular node is BST, the root is greater than all nodes on the left subtree and less than all nodes on the right subtree. However, is it sufficient condition? Let’s take a counterexample and prove that even root is greater than all nodes on the left side and smaller than all nodes on the right subtree, a binary tree may not be binary search tree. Look at the tree below.

In this tree above condition is satisfied, but we cannot call this binary tree a BST.

This is a recursive structure of a binary search tree that plays an important role. For a binary tree root at a node to be BST, it’s left subtree and right subtree should also be BST. So, there are three conditions which should be satisfied:

  1. Left subtree is BST
  2. Right subtree is BST
  3. Value of root node is greater than the max in the left subtree and less than minimum in right subtree

Check if binary tree is (BST) or not  : Recursive implementation

#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0

struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

Node * findMaximum(Node * root){
	if( !root ) return root;
	while( root->right ){
		root = root->right;
	}
	return root;
}

Node * findMinimum(Node * root){
	if( !root ) return root;
	while( root->left ){
		root = root->left;
	}
	return root;
}

int isBST(Node * node){

  	if(!node)
  		return true;
    
    if( ! ( node->left || node->right ) ) return true;   
  	int isLeft  = isBST(node->left);
  	int isRight = isBST(node->right);

  	if(isLeft && isRight){
  		/* Since we already know that left sub tree and
 		right sub tree are Binary search tree, finding min and max in them would be easy */
   	
   		Node *max  =  NULL;
   		Node *min  =  NULL;
   		if( node->left )
   			max = findMaximum(node->left);
   		if( node->right )
   			min = findMinimum(node->right);

   		//Case 1 : only left sub tree is there
    	if(max && !min)
        	return node->value > max->value;
   		//Case 2 : Only right sub tree is there
    	if(!max && min)
       		return node->value < min->value;
   		//Case 3 : Both left and right sub tree are there
    	return (node->value > max->value && node->value < min->value);
   }
   return false;
}

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 == NULL){
      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;
  //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);
  
  printf("%s", isBST(root ) ? "Yes" : "No" );
  
  return 0;
}

Check if binary tree is (BST) or not  : Optimized implementation

Above implementation to check if the binary tree is binary search tree or not is correct but inefficient because, for every node,  its left and right subtree are scanned to find min and max. It makes implementation non-linear.

How can we avoid re-scanning of left and right subtrees? If we can keep track max on left subtree and min on right subtree while checking those subtrees for BST property and use the same min and max.

Start with INTEGER_MAX and INTEGER_MIN, check if the root node is greater than max and less than min. If yes, then go down left subtree with max changed to root value, and go down to right subtree with min changed to root value. It is a similar implementation as above, except revisiting nodes.

#include<stdio.h>
#include<stdlib.h>

#define true 1
#define false 0
#define INT_MIN -32999
#define INT_MAX 32999

struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

int isBSTHelper(Node *root, int max, int min){
    if(!root) return true;

    if(root->value < min || root->value > max){
        return false;
    }

    return isBSTHelper(root->left, root->value, min) &&
           isBSTHelper(root->right, max, root->value);
}

int isBST(Node *root){
    return isBSTHelper(root, INT_MAX, INT_MIN);
}


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 == NULL){
      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;
  //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);
  
  printf("%s", isBST(root ) ? "Yes" : "No" );
  
  return 0;
}

The complexity of the above implementation is O(n) as we are traversing each node only once.

Another method to see if the binary tree is BST or not is to do an inorder traversal of the binary tree and keep track of the previous node. As we know in-order traversal of a binary search tree gives nodes in sorted order, previously visited node should be always smaller than the current node. If all nodes satisfy this property, a binary tree is a binary search tree. If this property is violated at any node, the tree is not a binary search tree.

The complexity of this implementation is also O(n) as we will be traversing each node only once

Please share if there is something missing or not correct. If you want to contribute and share your knowledge with thousands of learner around the world, please reach out to us at [email protected]

Closest element in binary search tree

Closest element in a binary search tree

The problem statement is: given a binary search tree and a value, find the closest element to that value in the binary search tree. For example, if below is the binary search tree and value given is 16, then the function should return 15.

closest element in binary search tree
Closest element in a binary search tree

Closest element in BST: thoughts

A simple approach is to go to all nodes of BST and find out the difference between the given value and value of the node. Get the minimum absolute value and add 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 say given value is k.

What if current.value is equal to the k? That means it is the closest node to the k and we cannot go better than this. Return the node value as closest value.

If current.value is greater than k, by virtue of BST, we know that nodes on the right subtree of the current node would be greater than the current.value. Hence the difference between k and all the nodes on the right subtree would only increase. So, there is no node on the right side, which is closer than the current node itself. Hence, the right subtree is discarded. If there is no left subtree, return current.value.

If current.value is less than k,  with the same logic above, all elements in left subtree are less than the value of current.value, the difference between k and the nodes on left subtree would only increase. So, we can safely discard the left subtree. If there is no right subtree, return current.value.

When we return the closest element from left subtree, we check if the difference between current.value and k less than difference between returned value and k. If it is less, then return current.value else return the returned value from the subtree.

Closest element in a binary search tree: algorithm

  1. If k == current.value, return current.value.
  2. If k < current.value, search the closest element in left subtree including the root as current is still a candidate.
    1. Return current.value if there is no left subtree.
  3. If k > current.value, search the closest element in the right subtree.
    1. Return current.value if there is no right subtree.
  4. If abs(current.value - k ) < abs(returnedValue - k ), return current.value else return returnedValue

Closest element in binary search tree: implementation

package com.company.BST;

/**
 * Created by sangar on 3.11.18.
 */
public class ClosestElement {

    public int findClosest(TreeNode node, int k){
        if(node == null) return -1;

        int currentValue = (int)node.getValue();

        if(currentValue == k) return currentValue;

        if(currentValue > k){
            if(node.getLeft() == null) return currentValue;

            //Find closest on left subtree
            int closest = findClosest(node.getLeft(), k);
            if(Math.abs(closest - k) > Math.abs(currentValue - k)){
                return currentValue;
            }
            return closest;
        }
        else {
            if (node.getRight() == null) return currentValue;

            //Find closest on right subtree
            int closest = findClosest(node.getRight(), k);
            if (Math.abs(closest - k) 
				> Math.abs(currentValue - k)) {
                return currentValue;
            }
            return closest;
        }
    }
}
package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

    public void setRight(TreeNode node){
        this.right = node;
    }

    public void setLeft(TreeNode node){
        this.left = node;
    }
}

package test;

import com.company.BST.BinarySearchTree;
import com.company.BST.ClosestElement;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class ClosestElementTest {

    ClosestElement tester = new ClosestElement();

    @Test
    public void closestElementTest() {

        BinarySearchTree<Integer> binarySearchTree =
						new BinarySearchTree<>();
        binarySearchTree.insert(10);
        binarySearchTree.insert(8);
        binarySearchTree.insert(15);
        binarySearchTree.insert(12);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);

        assertEquals(6,
			tester.findClosest(binarySearchTree.getRoot(),1));
    }
}

Complexity of algorithm to find closest element in a binary search tree is O(n) if tree is completely skewed.

Please share if there is something wrong or missing. If you are preparing for interviews, please signup for free interview material.

Two nodes with given sum in binary search tree

Two nodes with a given sum in a binary search tree

Given a binary search tree and an integer k, find all two nodes with given sum, nodes (a,b) such that a+b =k. In other words, find two nodes in a binary search tree which add to a number. For example, in the binary search tree given below, if k = 24, node(5) and node(19) should be the result.

sum of two nodes

Two nodes with given sum in binary search tree: thoughts

We have solved a similar problem with arrays, where we had to find pairs with a given sum k, the basic idea was that if the array is sorted, we will scan it from start(moving right) and end(moving left), and see if elements at two ends add up to k. If the sum of those numbers is greater than k, we move to right from start. If the sum of those two numbers is less than k, we move to left from end. We continue till two pointers cross each other.

Is there a way in which binary search tree can be sorted array? Yes, if BST is traversed in inorder, output is in sorted order of nodes. So, if we scan the BST and store in an array, the problem is same as find pairs in an array with a given sum. 
However, the solution requires two scans of all nodes and additional space of O(n).

Another solution could be to use a hash map. Each node is stored in the hashmap and at each node, we check if there is a key (sum-node.value) present in the hashmap. If yes, then two nodes are added into the result set. This still requires additional space, however, there is only one traversal of the tree.

How can we avoid additional space? Look at the binary search tree property: all the nodes on the left subtree of a root node are less than and all the nodes on right subtree are greater than the root node.
We know that the minimum node in BST is the leftmost node and the maximum node is the rightmost node.
If we start an inorder traversal, the leftmost node is the first node to be visited and if we do a reverse inorder traversal, the rightmost node is the first node will be visited. If the sum of the minimum and the maximum is less than k, then we have to go to the second minimum (next node in forward inorder traversal). Similarly, if the sum of the minimum and the maximum is greater than k, then we have to go to the second maximum(next in reverse inorder traversal)

How can we do a forward and reverse inorder traversal at the same time? 

Sum of two nodes in binary search tree: stacks

We know how to traverse a tree using stack data structure. We will use two stacks, one stack stores the nodes to be visited in forward inorder traversal and second stores the nodes to be visited in reverse inorder traversal. When we reach the leftmost and the rightmost node, we pop from the stacks and check for equality with the given sum.
If the sum of the two nodes is less than k, we increase one of the nodes. We will go to the right subtree of the node popped from the forward inorder stack. Why? Because that’s where we will find the next greater element.

If the sum of the two nodes is greater than k, we decrease one of the nodes. We will go to the left subtree of the node popped from the reverse inorder stack. Why? Because that’s where we will find the next smaller element.

We will continue till both forward and reverse inorder traversal do not meet.

Two nodes with given sum in BST: Implementation

package com.company;

import com.company.BST.TreeNode;
import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 26.11.18.
 */
public class TwoNodesWithGivenSum {
    public ArrayList<Pair<Integer, Integer>>
		findPairsWithGivenSum(TreeNode root, int sum) {

        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();

        ArrayList<Pair<Integer, Integer>> result
			= new ArrayList<>();

        TreeNode cur1 = root;
        TreeNode cur2 = root;

        while (!s1.isEmpty() || !s2.isEmpty() ||
                cur1 != null || cur2 != null) {
            if (cur1 != null || cur2 != null) {
                if (cur1 != null) {
                    s1.push(cur1);
                    cur1 = cur1.getLeft();
                }

                if (cur2 != null) {
                    s2.push(cur2);
                    cur2 = cur2.getRight();
                }
            } else {
                int val1 = (int)s1.peek().getValue();
                int val2 = (int)s2.peek().getValue();

                if (s1.peek() == s2.peek()) break;

                if (val1 +  val2 == sum)
					result.add(new Pair(val1, val2)) ;

                if (val1 + val2 < sum) {
                    cur1 = s1.pop();
                    cur1 = cur1.getRight();
                } else {
                    cur2 = s2.pop();
                    cur2 = cur2.getLeft();
                }
            }
        }

        return result;
    }
}

Test cases

package test;

import com.company.BST.BinarySearchTree;
import com.company.TwoNodesWithGivenSum;
import javafx.util.Pair;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class TwoNodesWithGivenSumTest {

    TwoNodesWithGivenSum tester = new TwoNodesWithGivenSum();

    @Test
    public void twoNodesWithGivenSumTest() {

        BinarySearchTree<Integer> binarySearchTree
			= new BinarySearchTree<>();
        binarySearchTree.insert(10);
        binarySearchTree.insert(8);
        binarySearchTree.insert(15);
        binarySearchTree.insert(12);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);

        ArrayList<Pair<Integer, Integer>> result
			= new ArrayList<>();
        result.add(new Pair(12,15));

        assertEquals(result, 
			tester.findPairsWithGivenSum(
				binarySearchTree.getRoot(),
				27
			)
		);
    }

    @Test
    public void twoNodesWithGivenSumNotPossibleTest() {

        BinarySearchTree<Integer> binarySearchTree
			= new BinarySearchTree<>();
        binarySearchTree.insert(10);
        binarySearchTree.insert(8);
        binarySearchTree.insert(15);
        binarySearchTree.insert(12);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);

        ArrayList<Pair<Integer, Integer>> result 
			= new ArrayList<>();
        assertEquals(result,
			tester.findPairsWithGivenSum(
				binarySearchTree.getRoot(),
				45
			)
		);
	}

    @Test
    public void twoNodesWithGivenSumNullTreeTest() {

        ArrayList<Pair<Integer,Integer>> result
			= new ArrayList<>();

        System.out.println(result);

        assertEquals(result,
			tester.findPairsWithGivenSum(
				null,
				45
			)
		);
    }
}

The complexity of this method to find two nodes with a given sum in a binary search tree is O(n). We are storing nodes in stacks, which will have space complexity of O(n), however, it is less than the previous solutions as it actually making the recursive stack explicit.

Please share if you have any doubts or something is missing or wrong. If you are preparing for an interview, signup to receive a free interview kit.