Register

GO Classes DPP | PYTHON & DSA |BST

357 views
3 3 votes

Suppose we convert a balanced Binary Search Tree (BST) containing $n$ elements into a Sorted Doubly Linked List (DLL) in-place (without using extra memory for new nodes). What is the time complexity of the most efficient algorithm to perform this conversion, and what is the height of the tree if it were converted back into a Complete Binary Tree?

  1. $\Theta(n),\left\lfloor\log _2 n\right\rfloor$
     
  2. $\Theta(n \log n),\left\lceil\log _2 n\right\rceil$
     
  3. $\Theta(n),\left\lceil\log _2(n+1)\right\rceil-1$
     
  4. $\Theta\left(n^2\right),\left\lfloor\log _2 n\right\rfloor$

2 Answers

0 0 votes
During the traversal, we adjust the $\verb|left|$ pointer of each node to point to its predecessor and the $\verb|right|$ pointer to point to its successor.

Since we visit each node exactly once and perform $O(1)$ pointer adjustments per node, the total time complexity is $\Theta(n)$.

A complete binary tree with $n$ nodes has a height of $\text{floor}(\log _2 n)$
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | PYT...Next → · GO Classes DPP | DIG...
← Previous in category · GO Classes DPP | PYT...Next in category → · Python Interning con...
Position:
Show:

Related questions

0 0 votes
1 1 answer
220
220 views
GO Classes asked Feb 27
220 views
GO Classes DPP | PYTHON & DSA |HASHING
A hash table of size $M=11$ uses the hash function $h(k)=k \bmod 11$. QUADRATIC PROBING is used for collision resolution with the probing function $h(k, i)=\left(h(k)+i^2...
2 2 votes
1 1 answer
200
200 views
GO Classes asked Feb 27
200 views
GO Classes DPP | PYTHON & DSA |DIJKSTRA’S ALGO
Let $G=(V, E)$ be a directed graph with source vertex $s$. We run DIJKSTRA'S ALGORITHM to find the shortest paths. During the execution, the "Relaxation" step is performe...
2 2 votes
1 1 answer
196
196 views
GO Classes asked Feb 27
196 views
GO Classes DPP | PYTHON & DSA |DEQUE
A double-ended queue (DEQUE) supports insertion and deletion at both ends $(f$ for front, $r$ for rear$)$. If we want to implement a STACK using this DEQUE, which of the ...
1 1 vote
1 1 answer
164
164 views
GO Classes asked Feb 27
164 views
GO Classes DPP | PYTHON & DSA |QUICKSORT
Consider the QUICKSORT algorithm applied to an array of $n$ distinct elements. Let the pivot always be chosen as the MEDIAN of the array. What is the recurrence relation ...