Question

when doing left and right rotation of a binary search tree: Do I have to preserve...

when doing left and right rotation of a binary search tree: Do I have to preserve all in, post and pre-order or just one order ?

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

In order of a BST should always yield output in sorted order so it must be preserved.

Pre-order and post order can change depending upon the rotations

as we can see in the case of

X     

Y

Z

We have after rotation say

Y

Z X

Then we can see the pre-order in the earlier case was XYZ and in the second case the preorder becomes YZX so it is not same

postorder is ZYX but in second case it is ZXY so it can also change but inorder is always

ZYX in both cases

Do give a thumbs up

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
You are given a reference to the root node of a binary search tree, that implements...
You are given a reference to the root node of a binary search tree, that implements a dictionary data structure. Please print all the elements in depths 500 through 510, all in sorted order. A node in a binary search tree is at depth x, if it takes x hops to get from the root. So the root is at depth 0, the children of the root are at depth 1, and so on. The class TreeNode defines a single...
Binary Search Tree with multiple structs? Hi, I am having an issue with trying to create...
Binary Search Tree with multiple structs? Hi, I am having an issue with trying to create a binary search tree while having multiple structs. The struct code provided is provided for us. #define CAT_NAME_LEN 25 #define APP_NAME_LEN 50 #define VERSION_LEN 10 #define UNIT_SIZE 3 struct app_info{ char category[CAT_NAME_LEN]; // name of category char app_name[APP_NAME_LEN]; // name of application char version[VERSION_LEN]; // version number float size; // size of application char units[UNIT_SIZE]; // GB or MB float price; // price in...
Binary Search Tree Code in Java Write a program that prompts user to enter however many...
Binary Search Tree Code in Java Write a program that prompts user to enter however many numbers they want to add to the binary search tree. Then have the user input numbers until the tree contains that many elements. If the user enters a number that already exists in the tree, then a message should be displayed "Number is already in the tree". Once all elements are added to the tree print its contents in sorted order. Assume all user...
‏What is the output of the Euler tour in the normal binary search tree if the...
‏What is the output of the Euler tour in the normal binary search tree if the key insert order is 5 , 2 , 8 , 5 , 9 , 5 , 1 , 3 , 4 , 2 , 8 ? All keys equal to the node should be the right subtree of that node. ____________________________________________________________ ‏Construct the binary max - heap for the keys given below. Once all the keys are inserted, perform the remove maximum operation, and...
The one missing piece was inserting into a binary search tree; we'll take care of that...
The one missing piece was inserting into a binary search tree; we'll take care of that today and write the insert function, as well as a height function. Both functions will be implemented in the "bst.h" header file, and tested using a provided main program in "main.cpp". Step one is to implement the insert function --- go ahead and modify "bst.h", adding the necessary code to (1) allocate a new node, and (b) link it into the tree. Once you...
Here is a picture of a Binary Search Tree. First, construct the Binary Search Tree using...
Here is a picture of a Binary Search Tree. First, construct the Binary Search Tree using the following BinaryNode as we discussed in class. public class BinaryNode { private int value; private BinaryNode leftChild; private BinaryNode rightChild; public BinaryNode(int value) { this.value = value; leftChild = null; rightChild = null; } public BinaryNode(int value, BinaryNode leftChild, BinaryNode rightChild) { this.value = value; this.leftChild = leftChild; this.rightChild = rightChild; } public int getValue() { return value; } public void setValue(int value)...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None:...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None: """This method adds new value to the tree, maintaining BST property. Duplicates must be allowed and placed in the right subtree.""" Example #1: tree = BST() print(tree) tree.add(10) tree.add(15) tree.add(5) print(tree) tree.add(15) tree.add(15) print(tree) tree.add(5) print(tree) Output: TREE in order { } TREE in order { 5, 10, 15 } TREE in order { 5, 10, 15, 15, 15 } TREE in order {...
how to pass in an object from an array of objects in a binary search on...
how to pass in an object from an array of objects in a binary search on swift? I have the following:    func binarySearchPrefix(array: [String], target: String) -> Bool {                var left = 0         var right = array.count - 1                while (left <= right) {             let mid = (left + right) / 2             let value = array[mid]             if (value.hasPrefix(target)) {                 return true             }             if (value < target) {                ...
This assignment involves using a binary search tree (BST) to keep track of all words in...
This assignment involves using a binary search tree (BST) to keep track of all words in a text document. It produces a cross-reference, or a concordance. This is very much like assignment 4, except that you must use a different data structure. You may use some of the code you wrote for that assignment, such as input parsing, for this one. Remember that in a binary search tree, the value to the left of the root is less than the...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT