This week we talked a bit more about binary trees, including a new type called the binary search tree. A BST is very useful in sorting numbers since every single node follows the same pattern: values smaller than the parent go to the left subtree and values greater than go to the right subtree. Since this pattern is preserved throughout the entire search tree, recursion is almost a must when thinking about these structures. Of course, this layout makes searching for values much easier since half of the tree can be ignored each time (in an average, well-balanced tree); I find the structure very intuitive and I'd like to know if binary search trees have important applications in software design or other topics in computer science.
In exercise 3, we dealt with writing methods to construct a binary tree from its preorder and inorder traversals, as well as finding the sum of the deepest path of a tree. In particular, I enjoyed coding the first problem, since it was something new I'd never seen before and provided a good challenge. Unlike some of the lab problems about linked lists/binary trees, this exercise went by faster and I found myself solving the problem much faster and with a greater understanding than before. My basic approach to question 1 was to first find the root, partition the inorder list into left and right subtrees, and repeat the process all over again. For question 2, which was the sum_to_deepest function, I had a bit more trouble since I first had no idea how to keep track of each path along with its sum. In the end, I settled for keeping a list of unique paths along with their sums instead of replacing the values for sum each time a greater value popped up.
Assignment 2, part 2 was posted a week back and I should probably work on it soon considering I've only looked at the instructions. Right now, I'm still trying to understand how to approach each method, but I hope that my finished code will be clear and correct.
No comments:
Post a Comment