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

answered: 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?

answered: Guest

answer; insurance cards, drivers licenses,and payment cards for fuel;

i believe the above answer to be correct;

answered: Guest

its true for the one time

Other questions on the subject: Computers and Technology

Computers and Technology, 24.06.2019 10:20, Cobetate

Multiple choice project create a program with two multiple choice questions. 1. users have two attempts only, show attempt number each time. hint: while loop with break control. (20%) 2. only one correct answer for each question, use switch case for each question. (20%) 3. show total score after the two questions are answered. hint: . (20%) 4. user have options to answer the two questions again if first attempt score is not 100%. hint: if statment. (20%) 5. use string method .toupper() to allow users to enter with lowercase or uppercase letters. (20%) 1. where is the capital of the state of florida? a. orlando b. tallahassee c. miami d. tampa b 2. where is walt disney world park located in florida? a. orlando b. tallahassee c. miami d. tampa a

Answers: 1

continue

Computers and Technology, 24.06.2019 18:30, shemiahking5432

Jacking is a crime that takes place when a hacker misdirects url to a different site. the link itself looks safe, but the user is directed to an unsafe page

Answers: 1

continue

Computers and Technology, 24.06.2019 20:30, michell200428

Drums installed, you would apply clicks of the parking brake to obtain a slight drag on both rear wheels

Answers: 1

continue

Computers and Technology, 25.06.2019 10:20, lydialinton23

Write a program that lets the user play the game of rock, paper, scissors against the computer. the program should work as follows. 1. when the program begins, a random number in the range of 1 through 3 is generated. if the number is 1, then the computer has chosen rock. if the number is 2, then the computer has chosen paper. if the number is 3, then the computer has chosen scissors. (don’t display the computer’s choice yet.) 2. the user enters his or her choice of “rock”, “paper”, or “scissors” at the keyboard. (you can use a menu if you prefer.) 3. the computer’s choice is displayed. 4. a winner is selected according to the following rules: • if one player chooses rock and the other player chooses scissors, then rock wins. (the rock breaks the scissors.) • if one player chooses scissors and the other player chooses paper, then scissors wins. (scissors cuts paper.) • if one player chooses paper and the other player chooses rock, then paper wins. (paper wraps rock.) • if both players make the same choice, the game must be played again to determine the winner. be sure to divide the program into functions that perform each major task. include the code and the console output from running your program with test inputs in your report.

Answers: 3

continue

Do you know the correct answer?

:

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