# Recursion Problems with trees (* know for exam)

- *Insert a new node into a BST tree (O(lg n) in a balanced tree, O(n) in an unbalanced)
- *Search a tree for a value (O(lg n) in a balanced tree, O(n) in an unbalanced)
- *Inorder traversal of a BST tree with printout in numerical order
- *Preorder and postorder traversals.
- *Delete a node from the tree.
- Convert a tree to it mirror(the children of every node are swapped)
- *Return the Height of a tree.
- *Return the depth of a specific node in the tree. ie(distance from root, root has a depth of 0)
- *Return the sum of the node values in a tree.
- *Return the number of nodes in a tree.
- *Return the number of leaves in a tree.
- Return the IPL of a BST tree. Don’t use a global variable here! The internal path length is a nice measure of how well balanced a tree is. If you create a tree using random numbers the expected ipl will be 1.386*TREESIZE*log
_{2}(TREESIZE) – 2.846*TREESIZE. What is the minimum and maximum IPL of a tree of N nodes?
- *Augment the nodes in a tree with a size variable. Write a recursive method that fills the size variable with the number of nodes in the subtree determined by that node.
- (assume size variable is filled) Return the rank(k) of a node. # number of values in a tree strictly less than k. Do in O(lg n) .
- (assume size variable is filled) Return the range(k1,k2) # number of values in tree so that k1 <= value < k2. Do in O(lg n)
- Write bool isBST(). returns true if a BST and false otherwise.
- Augment the nodes in a tree with a sumToRoot int variable. Fill in this variable for the tree. Also implement insert(val) and delete(val) for this tree so that the sumToRoot variables are appropriately updated.
- Balance a tree from scratch. See DSW algorithm.
- Merge two BST trees.
- Create a sorted linked list containing the leaves of a BST.
- Convert BST tree to ordered doubly linked list(a very cool problem that takes some thinking)
- Find the LCA of two nodes in the BST. LCA is the lowest common ancestor.