A tree is a data structure that consists of nodes in a parent / child relationships, and these nodes are connected via an edge (can be called branches too). Each node can point to multiple other nodes and when you draw it out it has a "tree" like structure except it generally goes from top to bottom where a tree would grow upwards. Trees are nonlinear so unlike a linked list you encounter branches, and their nodes are generally going to be strings and numbers but they can also be other data types as well. A BST node can only point to children, and not siblings, so each node is moving away from the root, the top node of the tree. Some other terminology would be siblings with are nodes that have the same parent ally a leaf which is a node with no children.
The most common example of a tree is the HTML DOM. Opening up a website and inspecting element you can just console the children and nodes and is kinda fun to play around with. Trees are also used in machine learning, which I'd love to get into one day but that's gonna be another day or week or month. One thing that you would probably encounter daily and not realize it, is your projects and whatever text editor you use (should be VS Code), the folder structure is in a tree like structure.
A binary search tree has special conditions that other trees do not and that is a node can have a maximum of 2 children, and that is the binary part. They are also kept in a specific order, and are generally used to store data for comparisons, whether it be number or strings (the 2 most common). So whatever value is on the root, smaller items go to the left and larger items/values are stored to the right, and this continues as you go to children. Because data is sorted in binary search trees, searching through them is very efficient. It is very similar to the divide and conquer method but it's already done for us. I'll be visiting a few algorithms after I have the data structure portion "done". Compare and then right or left based on smaller or larger and repeat. One thing we never talked about are duplicate values. Comparing less than or equal too is great and all but what happens when the values are the same? An easy way to handle it would be to just return false or undefined but then again you could add a frequency value on that specific node, but that really is up to the programmer to make that decision. I'm not really sure what I'd do as I've never created one in a real world scenario but I like the idea of a counter, I feel like if the data was entered it should be stored somehow.
I thought about breaking this next section up but have decided to throw it in here. I'm going to be working through tree traversals here, which basically is an algorithm to visit every node on a tree. It is also, from what I've been gathering, a very common problem on coding interviews. Unliked a linked list there are many ways to traverse a tree where with a linked list there is a limited amount (1 or 2 depending on singly or doubly linked list). The easiest way to do this is through recursion, which in my dumb terms is basically calling the same method over and over again until it completes the task (potential for infinite loops...). Let me also say I barely understand the concept of recursion so I probably need to be revisiting recursion on a weekly if not daily basis. I do implement recursive functions in my code base when I can. Even though recursion may be a better and more efficient way of doing it, you can always write these methods iteratively as well. Two ways of traversing trees are:
- Breadth First Search (BFS) - working across the tree, which is basically a horizontal traverse, going one row/level at a time (sibling nodes before children).
- Depth First Search (DFS) - going down a tree then back up. But with the DFS there are multiple orders in which you can go, which I'll talk about.
Binary Search Tree. So now that we have done traversals we have to discuss when to use BFS vs DFS and then talk about the multiple ways in which a DFS can be done. We'll talk first just BFS vs DFS. If you have a tree that is a max width capacity (each parent has its maximum of 2 children BST!!!!!!!), we will have to store tons of data in our Queue and that would take up a bunch of memory, where in DFS we are not storing nodes across the siblings rather than individual left and right nodes. Time would be equal on both but in this scenario a DFS would take up less space (memory). If a tree is very much like a linked list (which it can be), then the BFS is more convenient since we are adding/removing from the queue at each node visit and in this scenario, the DFS would take up more more space. I think generally speaking you will see trees that are more flushed out, or tree like, vs list like, but again this is speculation by me since I have never actually used one outside of creating HTML elements and I didn't realize it was one until I started learning about this subject.
One thing I totally forgot to mention is that during my learning process I am focusing on 2 main sources.
- Algo Expert Crash course on data structures, and doing as many of their problems as I can.
- JS Algorithms and Data Structures Masterclass I'm also watching misc YouTube videos here and there to try and get some extra explanation when I do not fully understand what is going on. So quite a bit of what I am writing out here is word for word at times from all of these sources. I am not taking any credit for this, I just feel like for myself if I type/write it out and try to explain it in my own words I retain it a bit better. I will also say that I'm going to revisit these courses and these posts over and over again to really try and make sure all of this information sticks, since the goal is to learn and not just memorize.
Top comments (0)