Home » Technical Interview Questions » Tree Interview Questions » Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree


Reading Time - 7 mins

Problem

Given a linked list. The elements of the linked list are in increasing order. Convert the given linked list into a highly balanced binary search tree.

A highly balanced binary search tree is a binary search tree in which the difference between the depth of two subtrees of any node is at most one.

Example

Input

1->2->3->4->5->6->7

Output

4 2 6 1 3 5 7

Explanation

Convert Sorted List to Binary Search Tree

The given linked list is converted to a highly balanced binary search tree. As in the given binary tree, the elements smaller than the root element are to the left of the root and the elements greater than the root element is to the right of the root, So the given tree is a binary search tree. Also, the difference between the depth of two subtrees of any node is 0 for all the nodes so this binary search tree is a highly balanced binary search tree.

Approach for Convert Sorted List to Binary Search Tree

We will use a trick to form a balanced binary search tree from the given linked list. In place of start creating a tree from the root, we will start creating a tree from the leaf.

  • We count the number of elements in the linked list.
  • Here first n/2 elements will form left subtree then one element will form the root and remaining elements will form the right subtree.
  • Using recursion we recursively construct the left subtree.
  • We create a root node.
  • Link the left subtree with the root node.
  •  We will recursively construct the right subtree from the remaining elements.
  • Link the right subtree with the root node.
  • While creating the tree we also keep increasing the pointer of the liked list to point to the next element each time.
READ  Balanced Binary Tree

Implementation for Convert Sorted List to Binary Search Tree

C++ code for Convert Sorted List to Binary Search Tree

// C++ implementation of above approach 
#include <bits/stdc++.h> 
using namespace std; 

/* Link list node */
class LNode 
{ 
  public: 
  int data; 
  LNode* next; 
}; 

/* A Binary Tree node */
class TNode 
{ 
  public: 
  int data; 
  TNode* left; 
  TNode* right; 
}; 

TNode* newNode(int data); 
int countLNodes(LNode *head); 
TNode* sortedListToBSTRecur(LNode **head_ref, int n); 


/* This function counts the number of 
nodes in Linked List and then calls 
sortedListToBSTRecur() to construct BST */
TNode* sortedListToBST(LNode *head) 
{ 
  /*Count the number of nodes in Linked List */
  int n = countLNodes(head); 

  /* Construct BST */
  return sortedListToBSTRecur(&head, n); 
} 

TNode* sortedListToBSTRecur(LNode **head_ref, int n) 
{ 
  /* Base Case */
  if (n <= 0) 
    return NULL; 

  /* Recursively construct the left subtree */
  TNode *left = sortedListToBSTRecur(head_ref, n/2); 
  TNode *root = newNode((*head_ref)->data); 
  root->left = left; 

  *head_ref = (*head_ref)->next; 

  /* Recursively construct the right 
    subtree and link it with root 
    The number of nodes in right subtree 
    is total nodes - nodes in 
    left subtree - 1 (for root) which is n-n/2-1*/
  root->right = sortedListToBSTRecur(head_ref, n - n / 2 - 1); 

  return root; 
} 



/* UTILITY FUNCTIONS */

/* A utility function that returns 
count of nodes in a given Linked List */
int countLNodes(LNode *head) 
{ 
  int count = 0; 
  LNode *temp = head; 
  while(temp) 
  { 
    temp = temp->next; 
    count++; 
  } 
  return count; 
} 

void push(LNode** head_ref, int new_data) 
{ 
  /* allocate node */
  LNode* new_node = new LNode(); 
  
  /* put in the data */
  new_node->data = new_data; 

  /* link the old list off the new node */
  new_node->next = (*head_ref); 

  /* move the head to point to the new node */
  (*head_ref) = new_node; 
} 
void printList(LNode *node) 
{ 
  while(node!=NULL) 
  { 
    cout << node->data << " "; 
    node = node->next; 
  } 
} 

/* Helper function that allocates a new node with the 
given data and NULL left and right pointers. */
TNode* newNode(int data) 
{ 
  TNode* node = new TNode(); 
  node->data = data; 
  node->left = NULL; 
  node->right = NULL; 

  return node; 
} 

void preOrder(TNode* node) 
{ 
  if (node == NULL) 
    return; 
  cout<<node->data<<" "; 
  preOrder(node->left); 
  preOrder(node->right); 
} 

/* Driver code*/
int main() 
{ 
  /* Start with the empty list */
  LNode* head = NULL; 

  /* Let us create a sorted linked list to test the functions 
  Created linked list will be 1->2->3->4->5->6->7 */
  push(&head, 7); 
  push(&head, 6); 
  push(&head, 5); 
  push(&head, 4); 
  push(&head, 3); 
  push(&head, 2); 
  push(&head, 1); 

  cout<<"Given Linked List "; 
  printList(head); 

  /* Convert List to BST */
  TNode *root = sortedListToBST(head); 
  cout<<"\nPreOrder Traversal of constructed BST "; 
  preOrder(root); 

  return 0; 
}
Given Linked List 1 2 3 4 5 6 7
PreOrder Traversal of constructed BST 4 2 1 3 6 5 7

Java code for Convert Sorted List to Binary Search Tree

class LinkedList { 

  /* head node of link list */
  static LNode head; 
  
  /* Link list Node */
  class LNode 
  { 
    int data; 
    LNode next, prev; 

    LNode(int d) 
    { 
      data = d; 
      next = prev = null; 
    } 
  } 
  
  /* A Binary Tree Node */
  class TNode 
  { 
    int data; 
    TNode left, right; 

    TNode(int d) 
    { 
      data = d; 
      left = right = null; 
    } 
  } 
  TNode sortedListToBST() 
  { 
    /*Count the number of nodes in Linked List */
    int n = countNodes(head); 

    /* Construct BST */
    return sortedListToBSTRecur(n); 
  } 
  TNode sortedListToBSTRecur(int n) 
  { 
    /* Base Case */
    if (n <= 0) 
      return null; 

    /* Recursively construct the left subtree */
    TNode left = sortedListToBSTRecur(n / 2); 
    TNode root = new TNode(head.data); 

    // Set pointer to left subtree 
    root.left = left; 
    head = head.next; 
    root.right = sortedListToBSTRecur(n - n / 2 - 1); 

    return root; 
  } 

  /* UTILITY FUNCTIONS */
  /* A utility function that returns count of nodes in a 
  given Linked List */
  int countNodes(LNode head) 
  { 
    int count = 0; 
    LNode temp = head; 
    while (temp != null) 
    { 
      temp = temp.next; 
      count++; 
    } 
    return count; 
  } 
  void push(int new_data) 
  { 
    /* allocate node */
    LNode new_node = new LNode(new_data); 

    /* since we are adding at the begining, 
    prev is always NULL */
    new_node.prev = null; 

    /* link the old list off the new node */
    new_node.next = head; 

    /* change prev of head node to new node */
    if (head != null) 
      head.prev = new_node; 

    /* move the head to point to the new node */
    head = new_node; 
  } 
  void printList(LNode node) 
  { 
    while (node != null) 
    { 
      System.out.print(node.data + " "); 
      node = node.next; 
    } 
  } 

  void preOrder(TNode node) 
  { 
    if (node == null) 
      return; 
    System.out.print(node.data + " "); 
    preOrder(node.left); 
    preOrder(node.right); 
  } 
  public static void main(String[] args) { 
    LinkedList llist = new LinkedList(); 
    llist.push(7); 
    llist.push(6); 
    llist.push(5); 
    llist.push(4); 
    llist.push(3); 
    llist.push(2); 
    llist.push(1); 

    System.out.println("Given Linked List "); 
    llist.printList(head); 

    /* Convert List to BST */
    TNode root = llist.sortedListToBST(); 
    System.out.println(""); 
    System.out.println("Pre-Order Traversal of constructed BST "); 
    llist.preOrder(root); 
  } 
}
Given Linked List 1 2 3 4 5 6 7
PreOrder Traversal of constructed BST 4 2 1 3 6 5 7

Time complexity

O(n)  because we are traversing the linked list only once.

READ  Construct BST from given Preorder Traversal

Space complexity

O(n) because we are creating a tree of n nodes.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions