Register

GO Classes DPP | PYTHON & DSA |BST

• recategorized by
146 views
1 1 vote

A Binary Search Tree (BST) is constructed by inserting the following sequence of numbers into an initially empty tree:
$$
45,20,70,10,30,60,85,25,35
$$
After the tree is constructed, we perform a DELETE operation on the node with value $20$. In our implementation, if a node has two children, it is replaced by its in-order successor.

What is the resulting height of the tree after the deletion?

$($Note: Height is defined as the number of edges on the longest path from the root to a leaf node. The height of a single-node tree is $0 )$.

1 Answer

1 1 vote

Tree Construction: Root$(45)$. Left$: 20$, Right$: 70$. $20$'s children$: 10$, $30$ .$30$'s children$: 25$, $35$. $70$'s children: $60$, $85$.

Deletion of $\mathbf{20}:$ Node $20$ has two children $(10$ and $30)$. Its in-order successor is $25$.

Final Tree: Root$(45)$. Left$: 25$. $25$'s Left$: 10$, $25$'s Right$: 30$. $430$'s Right$: 35$.

Height Calculation: Path $45 \rightarrow 25 \rightarrow 30 \rightarrow 35$ has $3$ edges.

ANSWER$: 3$

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | PYT...Next → · GO Classes DPP | PYT...
← Previous in category · GO Classes DPP | PYT...Next in category → · GO Classes DPP | PYT...
Position:
Show:

Related questions

0 0 votes
1 1 answer
159
159 views
GO Classes asked Feb 18
159 views
GO Classes DPP | PYTHON & DSA |ASYMPTOTIC ANALYSIS
An algorithm $A$ solves a problem of size $n$ by dividing it into three subproblems, each of size $n / 2$. The "combine" step takes $O(n \log n)$ time. The recurrence rel...
0 0 votes
1 1 answer
132
132 views
GO Classes asked Feb 18
132 views
GO Classes DPP | PYTHON & DSA |GRAPH
Consider a directed graph $G$ with $V$ vertices and $E$ edges. We represent this graph using an Adjacency List where each vertex $u$ has a list of its outgoing edges. To ...
0 0 votes
1 1 answer
106
106 views
GO Classes asked Feb 18
106 views
GO Classes DPP | PYTHON & DSA |LINKEDLIST
Consider a singly linked list where each node has a $\verb|data|$ field and a $\verb|next|$ pointer. We have two pointers$: \verb|P|$ points to the first node, and $\verb...
0 0 votes
1 1 answer
122
122 views
GO Classes asked Feb 18
122 views
GO Classes DPP | PYTHON & DSA |STACK
Consider a scenario where you have an empty stack $S$ and an empty queue $Q$. You are given a sequence of $n$ distinct integers. You perform the following operations in o...