Also called an ordered or sorted binary tree, is where you take a group of data and turn them into a tree full of nodes where each left node is "lower" (dimensionally) than each right node. This tree starts at the "root node" and any node without children is called a "leaf node"
In this project we are to build a Balanced BST (since an unbalanced tree can lead to degeneration, so that lookup performance is deteriorated to that of linear search) from a sorted array, making sure to remove any possible duplicates in the array or tree.
Write a simple driver script that does the following:
- Create a binary search tree from an array of random numbers. You can create a function that returns an array of random numbers every time you call it, if you wish.
- Confirm that the tree is balanced by calling
isBalanced
- Print out all elements in level, pre, post, and in order
- Unbalance the tree by adding several numbers > 100
- Confirm that the tree is unbalanced by calling
isBalanced
- Balance the tree by calling
rebalance
- Confirm that the tree is balanced by calling
isBalanced
- Print out all elements in level, pre, post, and in order