Question

In: Computer Science

in C++, given a binary search tree of ints, in which each node contains a size...

in C++, given a binary search tree of ints, in which each node contains a size parameter (also an int), explain, in English, not code, how you would find the median element of the tree in theta(log N) time.

Solutions

Expert Solution

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

We can find kth element in BST where k=n/2 for median

Here's just an outline of the idea:

In a BST, the left subtree of node T contains only elements smaller than the value stored in T. If k is smaller than the number of elements in the left subtree, the kth smallest element must belong to the left subtree. Otherwise, if k is larger, then the kth smallest element is in the right subtree.

We can augment the BST to have each node in it store the number of elements in its left subtree (assume that the left subtree of a given node includes that node). With this piece of information, it is simple to traverse the tree by repeatedly asking for the number of elements in the left subtree, to decide whether to do recurse into the left or right subtree.

Now, suppose we are at node T:

  1. If k == num_elements(left subtree of T), then the answer we're looking for is the value in node T.
  2. If k > num_elements(left subtree of T), then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.
  3. If k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth smallest element in the left subtree.

The abovee algorithm requires O(log(n))

Kindly revert for any queries

Thanks.


Related Solutions

Create a binary search tree of stacks where each node contains a key and a stack.
IN C++   Create a binary search tree of stacks where each node contains a key and a stack. In this binary search tree, when adding a new element to the tree it is inserted based off of its key value; if that key value already exist then the element is pushed into the stack at that location, if the key value does not exist a node element is added to the tree to reflect that key, and a empty...
(IN C) Write the code to manage a Binary Tree. Each node in the binary tree...
(IN C) Write the code to manage a Binary Tree. Each node in the binary tree includes an integer value and string. The binary tree is sorted by the integer value. The functions include: • Insert into the binary tree. This function will take in as parameters: the root of the tree, the integer value, and the string. Note that this function requires you to create the node. • Find a node by integer value: This function takes in two...
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...
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...
IN JAVA Given a binary search tree, extract min operation finds the node with minimum key...
IN JAVA Given a binary search tree, extract min operation finds the node with minimum key and then takes it out of the tree. The program can be C++/Java or C-style pseudocode. Do not use function call to either Min or delete done in the class. Write this from scratch. (No need to ensure AVL properties, just show it for a generic BST) Node * extract min(Node * x) { }
c++ Binary Search Tree: find parent of a node please insert comment to explain what the...
c++ Binary Search Tree: find parent of a node please insert comment to explain what the code do. Use struct Node{ int data; Node* left; Node* right};
A binary tree is a rooted tree in which each node has at most two children....
A binary tree is a rooted tree in which each node has at most two children. Show by induction that in any binary tree the number of nodes with two children is exactly one less than the number of leaves.
Write a binary search tree with 10 nodes in Java, each node will have 3 attributes...
Write a binary search tree with 10 nodes in Java, each node will have 3 attributes (data, x, y). The binary tree need to have function "add()" to add new node into the tree. After added all 10 nodes, it will be sorted and turn into a balanced binary search tree.
write a method in java for a binary search tree that receives a node as input...
write a method in java for a binary search tree that receives a node as input and returns the successor node.
PYTHON CODING Using the structural node and methods discussed in Binary Search Tree below # Binary...
PYTHON CODING Using the structural node and methods discussed in Binary Search Tree below # Binary Tree Node structure class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.left = None self.right = None class BSTree(): def __init__(self, rootdata): self.root = Node(rootdata)    def insert(self, data, cur_node): if data < cur_node.data: if cur_node.left == None: cur_node.left = Node(data) else: self.insert(data, cur_node.left)    elif data > cur_node.data: if cur_node.right == None: cur_node.right = Node(data) else:...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT