Register

GO Classes DPP | PYTHON & DSA |TREE

306 views
2 2 votes

A GO Tree is a rooted binary tree defined as follows:
For every node $u$ (except the root): Let parent $(u)$ be the parent of $u$.
Define:

  • $\operatorname{Side}(u)=0$ if $u$ is a left child,
     
  • $\operatorname{Side}(u)=1$ if $u$ is a right child.

The tree satisfies the GO property if on every root-to-leaf path, the value of $\operatorname{Side}(u)$ changes at most once.

Consider a GO Tree with $n$ nodes.

Which of the following statements is/are necessarily true?

  1. A GO TREE CAN HAVE HEIGHT $n-1$
     
  2. EVERY ROOT-TO-LEAF PATH CONTAINS AT MOST ONE LEFT EDGE FOLLOWED BY A RIGHT EDGE
     
  3. A GO TREE WITH $n$ NODES CAN HAVE $\Theta(\log n)$ HEIGHT
     
  4. EVERY GO TREE IS A COMPLETE BINARY TREE

1 Answer

1 1 vote
Option A:
A path that always goes left (or always right) has zero flips, so a chain of n nodes is allowed. Hence height can be $n-1$.

Option B:
By definition, Side(u) can change at most once on any root-to-leaf path, so multiple alternations like $L \rightarrow R \rightarrow L$ are not allowed.

Option C:
A perfectly balanced tree where all left edges are taken first and right edges only after one level satisfies the Flip-Path property and has height $\Theta(\log n)$.

Option D:
False. The tree may be highly skewed or partially filled.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · #TokenringNext → · GO Classes DPP | PYT...
← Previous in category · GO Classes CS Test S...Next in category → · heap
Position:
Show:

Related questions

1 1 vote
1 1 answer
269
269 views
GO Classes asked Jan 1
269 views
GO Classes DPP | PYTHON & DSA |PYTHON
 data = {'a': 1, 'b': 2, 'c': 3} for key in data: if data[key] 1: del data[key] print(len(data))What happens when this code is executed?It prints $1$ It prin...
1 1 vote
1 1 answer
230
230 views
GO Classes asked Jan 1
230 views
GO Classes DPP | PYTHON & DSA |PYTHON
Predict the output of the following code:a = 256 b = 256 print(a is b) x = 257 y = 257 print(x is y)What is the output when run as a standard Python script?TRUE, TRUE TRU...
1 1 vote
1 1 answer
179
179 views
GO Classes asked Jan 1
179 views
GO Classes DPP | PYTHON & DSA |PYTHON
What will be the output of the following Python code snippet?data = {'a': 10, 'b': 20} print(data.get('c', 30) + data.get('a'))KeyError $40$ $30$ $60$
1 1 vote
1 1 answer
192
192 views
GO Classes asked Jan 1
192 views
GO Classes DPP | PYTHON & DSA |PYTHON
Given a list of integers numbers $=[1,2,3,4,5,6]$, which of the following list comprehensions correctly creates a new list containing the squares of only the even numbers...