Question

In: Computer Science

write a function that takes as input the root of a general tree and returns a...

write a function that takes as input
the root of a general tree and returns a binary tree generated by the conversion
process illustrated in java

Expert Solution

import java.util.*;

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

class BinaryTree {

static Set<TreeNode> set = new HashSet<>();

static Stack<TreeNode> stack = new Stack<>();

// Function to build tree using given traversal

public TreeNode buildTree(int[] preorder, int[] inorder)

{

TreeNode root = null;

for (int pre = 0, in = 0; pre < preorder.length;) {

TreeNode node = null;

do {

node = new TreeNode(preorder[pre]);

if (root == null) {

root = node;

}

if (!stack.isEmpty()) {

if (set.contains(stack.peek())) {

set.remove(stack.peek());

stack.pop().right = node;

}

else {

stack.peek().left = node;

}

stack.push(node);

} while (preorder[pre++] != inorder[in] && pre < preorder.length);

node = null;

while (!stack.isEmpty() && in < inorder.length &&

stack.peek().val == inorder[in]) {

node = stack.pop();

in++;

}

if (node != null) {

set.add(node);

stack.push(node);

}

return root;

}

// Function to print tree in Inorder

void printInorder(TreeNode node)

{

if (node == null)

return;

/* first recur on left child */

printInorder(node.left);

/* then print the data of node */

System.out.print(node.val + " ");

/* now recur on right child */

printInorder(node.right);

}

// driver program to test above functions

public static void main(String args[])

{

BinaryTree tree = new BinaryTree();

int in[] = new int[] { 9, 8, 4, 2, 10, 5, 10, 1, 6, 3, 13, 12, 7 };

int pre[] = new int[] { 1, 2, 4, 8, 9, 5, 10, 10, 3, 6, 7, 12, 13 };

int len = in.length;

TreeNode root = tree.buildTree(pre, in);

tree.printInorder(root);

}

venereology answered 1 year ago

Write a function that takes a number as input, and returns the character A if the...

Write a function that takes a number as input, and returns the character A if the input is 90 and above, B if it’s 80 and above but less than 90, C if it’s at least 70 but less than 80, D if it’s at least 60 but less than 70, and F if it’s less than 60. If the input is not a number or is negative, the function should exit 1 with an error (by calling the Matlab...

USING PYTHON, write a function that takes a list of integers as input and returns a...

USING PYTHON, write a function that takes a list of integers as input and returns a list with only the even numbers in descending order (Largest to smallest) Example: Input list: [1,6,3,8,2,5] List returned: [8, 6, 2]. DO NOT use any special or built in functions like append, reverse etc.

Write a C function called weighted_digit_sum that takes a single integer as input, and returns a...

Write a C function called weighted_digit_sum that takes a single integer as input, and returns a weighted sum of that numbers digits. The last digit of the number (the ones digit) has a weight of 1, so should be added to the sum "as is". The second from last digit (the tens digit) has a weight of 2, and so should be multiplied by 2 then added to the sum. The third from last digit should be multiplied by 1...

Write a PYTHON function CommonLetters(mystring) that takes mystring as input and returns the number of letters...

Write a PYTHON function CommonLetters(mystring) that takes mystring as input and returns the number of letters in mystring that also occur in the string ‘Python’. Using above function, write a program that repeatedly prompts the user for a string and then prints the number of letters in the string that are also in string ‘Python’. The program terminates when the user types an empty string.

PYTHON 3: Write a recursive function that takes a non-negative integer n as input and returns...

PYTHON 3: Write a recursive function that takes a non-negative integer n as input and returns the number of 1's in the binary representation of n. Use the fact that this is equal to the number of 1's in the representation of n//2 (integer division) plus 1 if n is odd. >>>numOnes(0) 0 >>>numOnes(1) 1 >>>numOnes(14) 3

Develop a function DNF that takes as input a proposition and returns as output a logically...

Develop a function DNF that takes as input a proposition and returns as output a logically equivalent proposition in DNF. Hint: Adapt the CNF function.

python 3 please Define a function voweliest that takes as input a string and returns as...

python 3 please Define a function voweliest that takes as input a string and returns as output a tuple where the string that has the most vowels in it is the first element and the second is the number of vowels in that string. Note: don't worry about ties or capital letters Hint: consider defining and using a separate function that counts the number of vowels in a given string

Write a recursive method using Java that takes a string s as input and returns a...

Write a recursive method using Java that takes a string s as input and returns a list that contains all the anagrams of the string s. An anagram is a word formed by rearranging the letters of a different word. For instance, the word ‘cat’ is an anagram of ‘act’. Notice that the output list cannot contain duplicates.

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns,...

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns, as output, the sum of the first n positive odd integers. Your solution should be recursive, and it should not contain any "for" loops or "while" loops.

(Binary Tree): Write a recursive implementation of the function, singleParent, that returns the number of the...

(Binary Tree): Write a recursive implementation of the function, singleParent, that returns the number of the nodes in a binary tree that have only one child. Convert it to an iterative version. in C++