Computers and Technology, 26.12.2021 01:00 brendonvernon8

: ${\huge{\underbrace{\overbrace{\color{aqua}{Question}}}}}$

Write an algorithm to do spiral order traversal of binary tree?

Answers: 1

Show answers

Answers

Answer from: brialevy2283

In level order traversal we make use of a single queue while in spiral order traversal we need use two stacks.

First stack('stackEven') is used to traverse the nodes at even level and second stack('stackOdd') is used to traverse the nodes at odd level.

Nodes at even level are stored in 'stackEven' and are pushed in it from left to right order whereas nodes at odd level are stored in 'stackOdd' and are pushed in it from right to left order.

Algorithm:

1. Push root node into the 'stackEven'. Set boolean 'evenLevel' to true. This boolean variable is used to indicate if the current level being visited is even level or odd level.

2. Now if 'evenLevel' is set to true repeat steps 2a to 2c until 'stackEven' is not empty.

2a. Pop the node from 'stackEven'. Let popped node be 'currentNode'. Print the value of 'currentNode'.

2b. If the right child of 'currentNode' is not null, push it into the 'stackOdd'.

2c. If the left child of 'currentNode' is not null, push it into the 'stackOdd'.

Notice that currentNode's right child is pushed first and then its left child is pushed.

3. If 'evenLevel' is not set to true then repeat steps 3a to 3c until 'stackOdd' is not empty.

3a. Pop the node from 'stackOdd'. Let popped node be 'currentNode'. Print the value of 'currentNode'.

3b. If the left child of 'currentNode' is not null, push it into the 'stackEven'.

3c. If the right child of 'currentNode' is not null, push it into the 'stackEven'.

Notice that currentNode's left child is pushed first and then its right child is pushed.

4. If 'evenLevel' is true set it to false and if it is false set it to true. This is because the next level visited would be odd if current level is even and vice versa.

5. Repeat steps 2-4 until both 'stackEven' and 'stackOdd' are not empty.

Implementation details could be found in function 'spiralTraversal(TreeNode root)' in the code snippet.

Example: Let's look at the state of the stacks as nodes in each level are visited for the following tree.

(attachment) 1.(see attachment 2)(attachment 3)

The time complexity of this algorithm is O(n) and extra space used is also O(n).

:

Write an algorithm to do spiral order traversal of binary tree?

Answer from: Quest

it on google i find it on there

Answer from: Quest

the answer will be d

Another question on Computers and Technology

Computers and Technology, 22.06.2019 00:30

These tools give presenters more freedom to move about the room and interact with their audience. laptop computer laser pointer lcd projector remote control

Answers: 2

Answer

Computers and Technology, 22.06.2019 01:00

)a grad student comes up with the following algorithm to sort an array a[1..n] that works by first sorting the first 2/3rds of the array, then sorting the last 2/3rds of the (resulting) array, and finally sorting the first 2/3rds of the new array. 1: function g-sort(a, n) . takes as input an array of n numbers, a[1..n] 2: g-sort-recurse(a, 1, n) 3: end function 4: function g-sort-recurse(a, `, u) 5: if u â’ ` â‰¤ 0 then 6: return . 1 or fewer elements already sorted 7: else if u â’ ` = 1 then . 2 elements 8: if a[u] < a[`] then . swap values 9: temp â† a[u] 10: a[u] â† a[`] 11: a[`] â† temp 12: end if 13: else . 3 or more elements 14: size â† u â’ ` + 1 15: twothirds â† d(2 â— size)/3e 16: g-sort-recurse(a, `, ` + twothirds â’ 1) 17: g-sort-recurse(a, u â’ twothirds + 1, u) 18: g-sort-recurse(a, `, ` + twothirds â’ 1) 19: end if 20: end function first (5 pts), prove that the algorithm correctly sorts the numbers in the array (in increasing order). after showing that it correctly sorts 1 and 2 element intervals, you may make the (incorrect) assumption that the number of elements being passed to g-sort-recurse is always a multiple of 3 to simplify the notation (and drop the floors/ceilings).

Answers: 3

Answer

Computers and Technology, 23.06.2019 06:00

Which statement is true of web-based social media? a.they allow consumers to interact with and update content. b.they cannot be updated easily, as compared to print media. c.they are expensive to produce and maintain, as compared to print and television. d.they can exist independent of the internet.

Answers: 1

Answer

Computers and Technology, 24.06.2019 03:30

Other - a written response, no less than arial 12-point font, to the following: of the following, which would you consider is most important to customer service goals? choose one and explain why. (1) accuracy (2) punctuality and attendance (3) courtesy (4) productivity (5) organization

Answers: 1

Answer

You know the right answer?

:

Write an algorithm to do spiral order traversal of binary tree?...

Questions