List to Tree

Moderate
0/80
1 upvote
Asked in companies
SalesforceAppleGoogle inc

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
1 4 5 8 9
6  
1 3 6 9 10 15
Sample Output 1:
1 4 5 8 9
1 3 6 9 10 15
Explanation of sample input 1:
For the first test case,

One of the valid BST will be:

altimage

Inorder traversal will be : [1, 4, 5, 8, 9]. Hence, the answer is  [1, 4, 5, 8, 9].

For the second test case, 

One of the valid BST will be:

altimage

Inorder traversal will be: [1,3,6,9,10]. Hence, the answer is [1,3,6,9,10].

Sample Input 2:
2
5
1 2 3 4 11
3
10 20 21
Sample Output 2:
1 2 3 4 11
10 20 21
Hint

Try to build the tree from the leaf node to the root node.

Approaches (2)
Modified Recursive 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’.
Time Complexity

O(N), where N is the number of nodes in the tree.

 

We are traversing each node present in the list and building the BST, the list contains N nodes. Hence, the overall time complexity is O(N).

Space Complexity

O(N), where N is the number of nodes in the tree.

 

We used N extra nodes to make the tree and  O(log (N)) space complexity for recursive stack during recursion calls in the worst case. So, the total space used is N + log(N). Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
List to Tree
Full screen
Console