Last Updated: 28 Oct, 2021

List to Tree

Moderate

Asked in companies

Solve now

Problem statement

Ninja is learning data structures and algorithms to excel in technical interviews. While practicing the questions of Linked List, he found a very interesting question in which a sorted doubly linked list is given,, and the task is to construct a balanced Binary search tree having the same elements as of the given Linked List. Can you help Ninja to solve this problem?

A balanced BST is defined as a binary search tree that follows a special property that the left and right subtrees of every node differ in height by no more than 1.

For Example:

If the given linked list is [1,4,5,8,9], then the balanced BST will :

Example

Note :

We will be using a single structure, ‘NODE’, to define both the List Node and Tree Node.
It will have the following members:
     1.  'VAL' to store the integer data value.
     2. 'PREV' pointer to store the address of the previous node and also used to store the address of the left child.
    3. 'NEXT' pointer to store the address of the next node and also used to store the address of the right child.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains the ‘N’ denoting the number of elements in the linked list.
The second line contains ‘N’ integers denoting the given linked list.

Output Format:

For each test case, print the inorder traversal of the constructed balanced BST.

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^6
1 <= nodeVal <=10^9

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will first find the number of elements present in the list using a ‘COUNTNODE(‘HEAD’)’ function. We will also define a REC(‘CURNODE’, ‘N’) that will return the root of the constructed BST of the first ‘N’ elements. We will first place the leftmost node, then the middle, then the right subtree similar to inorder manner. We will make the left subtree with ‘N’/2 nodes and the right subtree with the remaining nodes. While constructing the BST, we will store the ‘HEAD’ pointer in a global variable ‘CURNODE’ so that we keep moving the list head pointer to the next so that we have the appropriate pointer in each recursive call.

Algorithm:

Declare a global variable ‘CURNODE’.
Defining ‘COUNT_NODES’(‘HEAD’):
- Set ‘C’ as 0.
- Set ‘TEMP’ as ‘HEAD’.
- While ‘TEMP’ is not empty:
  - Set ‘C’ as ‘C’+1.
  - Set ‘TEMP’ as TEMP’s ‘NEXT’.
- Return ‘C’

Defining REC(’N’):
- If ‘N’ <= 0:
  - Return null node.
- Storing the left subtree in ‘LEFT’.
- Set ‘LEFT’ as REC(N/2).
- Declare a new node ‘ROOT’ and assign ROOT’s ‘VAL’ as CURNODE’s ‘VAL’.
- Shift the ‘CURNODE’ node to next of ‘CURNODE’.
- Link left subtree with the ‘ROOT’.
- Set ‘PREV’ of ‘ROOT’ as ‘LEFT’.
- Make the right subtree with the remaining nodes.
- Set ‘RIGHT’ as REC(’N’ - ‘N’/2 -1).
- Link right subtree with the ‘ROOT’.
- Set ‘NEXT’ of ‘ROOT’ as ‘RIGHT’.
- Return ‘ROOT’.

Set global variable ‘CURNODE’ as ‘HEAD’.
Declare ‘N’ to store the number of elements in the list.
Set ‘N’ as COUNT_NODE(‘HEAD’).
Set ‘ROOT’ as REC(’N’).
Return ‘ROOT’.

Solve now

02 Approach

In this approach, we will create a recursive function REC(‘CURNODE’) that will first find the middle of the linked list starting from ‘CURNODE’ using Floyd’s Algorithm (Hare and Tortoise Algorithm) and make a new node ‘ROOT’ having the ‘VAL’ as ‘VAL’ of the middle element. We are splitting the list in the middle because we have to follow the property of balanced BST. Now, we will make two recursive calls for the left and right subtree. In the end, we will return the ‘ROOT’ node.

Algorithm:

Defining REC(‘CURNODE’):
- If list contains zero or one element only.
- If ‘CURNODE’ is an empty node or ‘CURNODE.next is an empty node:
  - Return null node.
- Set ‘FAST’ as ‘CURNODE’.
- Set ‘SLOW’ as ‘CURNODE’.
- While ‘FAST’ is not empty and next of ‘FAST’ is not empty:
  - Set ‘SLOW’ as next of ‘SLOW’.
  - Set ‘FAST’ as next of FAST’s next.
- Now,’ SLOW’ will be pointing to the middle of the list.
- Split the list.
- Set ‘P’ as the previous node of ‘SLOW’.
- Set ‘N’ as the next node of ‘SLOW’.
- Set next of ‘P’ as an empty node.
- Set ‘PREV’ of ‘SLOW’ as an empty node.
- Set ‘PREV’ of ‘N’ as an empty node.
- Set ‘NEXT’ of ‘SLOW’ as an empty node.
- Make recursive calls for the left and right subtree.
- Set SLOW’s ‘PREV’ as REC(‘CURNODE’). (Left Subtree)
- Set SLOW’s ‘NEXT’ as REC(‘N’). (Right Subtree)
- Return ‘SLOW’.

Return REC(‘HEAD’).

Solve now