BSTSet

java.lang.Object
- BSTSet

public class BSTSet
extends java.lang.Object

A simple BST with int keys and no values

 Complete each function below.
 Write each function as a separate recursive definition (do not use more than one helper per function).
 Depth of root==0.
 Height of leaf==0.
 Size of empty tree==0.
 Height of empty tree=-1.
 Methods for you to write. Each of these public methods should call
 a recursive private method which you must also write.
 

 Group I - These don't modify the tree
 1. size - (This one is provided for you.) 
 2. height - height of the tree
 3. sizeOdd - number of Nodes with an odd key
 4. isPerfectlyBalancedS - at each Node, do left and right subtrees have same size?
 5. isPerfectlyBalancedH - at each Node, do left and right subtrees have same height?
 6. isOddBalanced - at each Node, do left and right subtrees contain the same number of odd keys?
 7. isSemiBalancedI - is each Node semibalanced? leaf or else size(larger child) / size (smaller child) <= 2
 8. sizeAtDepth - number of nodes at a given depth
 9. sizeLessThanDepth - number of nodes whose depth is < a given depth
 10. sizeGreaterThanDepth - number of nodes whose dept is > a given depth

 Group II - These method typically modify the tree
 11. removeOddSubtrees - remove subtrees whose root has an odd key
 12. removeLeaves - remove the leaves from the original tree
 13. removeSingles - remove nodes with exactly 1 child by replacing with its child
 14. removeDepthGreater - remove all subtrees whose dept is > given depth
 15. addZeroToSingles - For each node with just one child add key 0 as the other child
 16. sizeAtHeight - number of nodes which have a given height
 17. sizeLessThanHeight - number of nodes with height < a given height
 18. sizeGreaterThanHeight - number of nodes with height > a given height
 19. removeHeight - remove all subtrees with the given height in the original tree

Constructor Summary

Constructors
Constructor and Description

BSTSet()
Initializes an empty binary search tree with integer keys.

Constructors
Constructor and Description
`BSTSet()` Initializes an empty binary search tree with integer keys.

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`addZeroToSingles()` addZeroToSingles - For each node with just one child add key 0 as the other child Note: This will make every non-leaf node have 2 children.
`void`	`drawTree()` draws the tree on the StdDraw canvas
`static BSTSet`	`fromString(java.lang.String s)` Returns a new BSTSet with keys from the string s
`int`	`height()` height - height of the tree
`boolean`	`isOddBalanced()` isOddBalanced - at each Node, check if left and right subtrees contain the same number of odd keys.
`boolean`	`isPerfectlyBalancedH()` isPerfectlyBalancedH - at each Node, check if left and right subtrees have same height.
`boolean`	`isPerfectlyBalancedS()` isPerfectlyBalancedS - at each Node, checks if left and right subtrees have same size.
`boolean`	`isSemiBalancedI()` isSemiBalancedI - is each Node semibalanced? leaf or else two children and size(larger child) / size (smaller child) <= 2 A node with just 1 child is NOT semibalanced.
`java.lang.Iterable<java.lang.Integer>`	`levelOrder()`
`static void`	`main(java.lang.String[] args)`
`void`	`put(int x)` Adds the key x to this BSTset
`void`	`removeDepthGreaterThan(int k)` removeDepthGreater - remove all subtrees whose dept is > k
`void`	`removeHeight(int h)` removeHeight - remove all subtrees with height h in the original tree Hint: you will need to use the 'extra' member of Node and you will also need to modify the put method to update extra in affected nodes.
`void`	`removeLeaves()` removeLeaves - remove the leaves from the original tree
`void`	`removeOddSubtrees()` removeOddSubtrees - remove each subtree whose root has an odd key
`void`	`removeSingles()` removeSingles - remove nodes with exactly 1 child by replacing with its child
`int`	`size()` Returns the number of keys in this BSTset
`int`	`sizeAtDepth(int k)` sizeAtDepth - number of nodes at depth k
`int`	`sizeAtHeight(int h)` sizeAtHeight - number of nodes which have height h Hint: you will need to use the 'extra' member of Node and you will also need to modify the put method to update extra in affected nodes.
`int`	`sizeGreaterThanDepth(int k)` sizeGreaterThanDepth - number of nodes whose dept is > k
`int`	`sizeGreaterThanHeight(int h)` sizeGreaterThanHeight - number of nodes with height > h Hint: you will need to use the 'extra' member of Node and you will also need to modify the put method to update extra in affected nodes.
`int`	`sizeLessThanDepth(int k)` sizeLessThanDepth - number of nodes whose depth is < k
`int`	`sizeLessThanHeight(int h)` sizeLessThanHeight - number of nodes with height < h Hint: you will need to use the 'extra' member of Node and you will also need to modify the put method to update extra in affected nodes.
`int`	`sizeOdd()` sizeOdd - number of Nodes with an odd key
`java.lang.String`	`toString()`

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Constructor Detail
  - BSTSet
```
public BSTSet()
```
    Initializes an empty binary search tree with integer keys.
- Method Detail
  - addZeroToSingles
```
public void addZeroToSingles()
```
    addZeroToSingles - For each node with just one child add key 0 as the other child Note: This will make every non-leaf node have 2 children. Adding 0 will violate the binary search tree property, but is permitted for this method.
  - drawTree
```
public void drawTree()
```
    draws the tree on the StdDraw canvas
  - fromString
```
public static BSTSet fromString(java.lang.String s)
```
    Returns a new BSTSet with keys from the string s
    
    Parameters:
    s -
    
    Returns:
    a new BSTSet with keys from the string s
  - height
```
public int height()
```
    height - height of the tree
    
    Returns:
    the height of the tree
  - isOddBalanced
```
public boolean isOddBalanced()
```
    isOddBalanced - at each Node, check if left and right subtrees contain the same number of odd keys.
    
    Returns:
    true if every node's left and right subtrees have the same number of odd keys.
  - isPerfectlyBalancedH
```
public boolean isPerfectlyBalancedH()
```
    isPerfectlyBalancedH - at each Node, check if left and right subtrees have same height. Hint: The helper method should return -2 if not height balanced; otherwise, return the height of the subtree.
    
    Returns:
    true if every node's left and right subtrees have the same height.
  - isPerfectlyBalancedS
```
public boolean isPerfectlyBalancedS()
```
    isPerfectlyBalancedS - at each Node, checks if left and right subtrees have same size. Hint: The helper method should return -1 if not size balanced; otherwise the helper should return the size of the subtree.
    
    Returns:
    true if at every node's left and right subtrees have the same size; otherwise, false.
  - isSemiBalancedI
```
public boolean isSemiBalancedI()
```
    isSemiBalancedI - is each Node semibalanced? leaf or else two children and size(larger child) / size (smaller child) <= 2 A node with just 1 child is NOT semibalanced. Note: The condition for 2 children is NOT equivalent to size(larger child) <= 2 * size(smaller child) Hint: In the helper return -1 if the subtree is not semibalanced
    
    Returns:
    true if every node is semibalanced; a node is semibalanced if (a) it is a leaf or (b) it has two children and size(larger child) / size(smaller child) <= 2
  - levelOrder
```
public java.lang.Iterable<java.lang.Integer> levelOrder()
```
  - main
```
public static void main(java.lang.String[] args)
```
  - put
```
public void put(int x)
```
    Adds the key x to this BSTset
    
    Parameters:
    x -
  - removeDepthGreaterThan
```
public void removeDepthGreaterThan(int k)
```
    removeDepthGreater - remove all subtrees whose dept is > k
    
    Parameters:
    k - a specified depth
  - removeHeight
```
public void removeHeight(int h)
```
    removeHeight - remove all subtrees with height h in the original tree Hint: you will need to use the 'extra' member of Node and you will also need to modify the put method to update extra in affected nodes.
    
    Parameters:
    h - a specified height
  - removeLeaves
```
public void removeLeaves()
```
    removeLeaves - remove the leaves from the original tree
  - removeOddSubtrees
```
public void removeOddSubtrees()
```
    removeOddSubtrees - remove each subtree whose root has an odd key
  - removeSingles
```
public void removeSingles()
```
    removeSingles - remove nodes with exactly 1 child by replacing with its child
  - size
```
public int size()
```
    Returns the number of keys in this BSTset
    
    Returns:
    number of keys
  - sizeAtDepth
```
public int sizeAtDepth(int k)
```
    sizeAtDepth - number of nodes at depth k
    
    Parameters:
    k - a specified depth
    
    Returns:
    the number of nodes at depth k
  - sizeAtHeight
```
public int sizeAtHeight(int h)
```
    sizeAtHeight - number of nodes which have height h Hint: you will need to use the 'extra' member of Node and you will also need to modify the put method to update extra in affected nodes.
    
    Parameters:
    h - a specified height
    
    Returns:
    the number of nodes which have height h
  - sizeGreaterThanDepth
```
public int sizeGreaterThanDepth(int k)
```
    sizeGreaterThanDepth - number of nodes whose dept is > k
    
    Parameters:
    k - a specified depth
    
    Returns:
    the number of nodes whose depth is > k
  - sizeGreaterThanHeight
```
public int sizeGreaterThanHeight(int h)
```
    sizeGreaterThanHeight - number of nodes with height > h Hint: you will need to use the 'extra' member of Node and you will also need to modify the put method to update extra in affected nodes.
    
    Parameters:
    h - a specified height
    
    Returns:
    the number of nodes with height > h
  - sizeLessThanDepth
```
public int sizeLessThanDepth(int k)
```
    sizeLessThanDepth - number of nodes whose depth is < k
    
    Parameters:
    k - a specified depth
    
    Returns:
    the number of nodes whose depth is < k
  - sizeLessThanHeight
```
public int sizeLessThanHeight(int h)
```
    sizeLessThanHeight - number of nodes with height < h Hint: you will need to use the 'extra' member of Node and you will also need to modify the put method to update extra in affected nodes.
    
    Parameters:
    h - a specified height
    
    Returns:
    the number of nodes with height < h
  - sizeOdd
```
public int sizeOdd()
```
    sizeOdd - number of Nodes with an odd key
    
    Returns:
    number of Nodes with an odd key
  - toString
```
public java.lang.String toString()
```
    Overrides:
    
    toString in class java.lang.Object

Class BSTSet

A simple BST with int keys and no values

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

BSTSet

Method Detail

addZeroToSingles

drawTree

fromString

height

isOddBalanced

isPerfectlyBalancedH

isPerfectlyBalancedS

isSemiBalancedI

levelOrder

main

put

removeDepthGreaterThan

removeHeight

removeLeaves

removeOddSubtrees

removeSingles

size

sizeAtDepth

sizeAtHeight

sizeGreaterThanDepth

sizeGreaterThanHeight

sizeLessThanDepth

sizeLessThanHeight

sizeOdd

toString