Recursion Problems with trees (* know for exam)

  1. *Insert a new node into a BST tree (O(lg n) in a balanced tree, O(n) in an unbalanced)
  2. *Search a tree for a value (O(lg n) in a balanced tree, O(n) in an unbalanced)
  3. *Inorder traversal of a BST tree with printout in numerical order
  4. *Preorder and postorder traversals.
  5. *Delete a node from the tree.
  6. Convert a tree to it mirror(the children of every node are swapped)
  7. *Return the Height of a tree.
  8. *Return the depth of a specific node in the tree. ie(distance from root, root has a depth of 0)
  9. *Return the sum of the node values in a tree.
  10. *Return the number of nodes in a tree.
  11. *Return the number of leaves in a tree.
  12. 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*log2(TREESIZE) – 2.846*TREESIZE.  What is the minimum and maximum IPL of a tree of N nodes?
  13. *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.
  14. (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) .
  15. (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)
  16. Write bool isBST().  returns true if a BST and false otherwise.
  17. 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.
  18. Balance a tree from scratch. See DSW algorithm.
  19. Merge two BST trees.
  20. Create a sorted linked list containing the leaves of a BST.
  21. Convert BST tree to ordered doubly linked list(a very cool problem that takes some thinking)
  22. Find the LCA of two nodes in the BST.  LCA is the lowest common ancestor.

Comments are closed.