After a few adventures trying to solve binary tree algorithm problems, I thought it would be helpful to go through the basics of binary trees! The aim of this post is to help those who do not have a basis of knowledge on algorithms and datatypes.
When I talk about binary trees, I'm going to be specifically talking about binary search trees.
So, what is a binary tree?
A binary tree refers to a tree data structure, where each node has at most two children. These children are referred to as the left child (LC) and right child (RC). These children (LC and/or RC) can be null. Child nodes can have other children or a leaf, meaning they have no children.
A binary tree is referred to as "Strict" or "Proper" when each node has 0 or 2 children.
A "complete" binary tree means all levels except the last are completely filled and all nodes are as left as possible.
Why use trees?
A binary tree is a hierarchical data structure. It is a method that allows us to add order in how we store information. The order in which data is store optimizes the way we access and search for information. This makes sense as to why they are commonly used in algorithm problems, because they can reduce the amount of time or space it takes up when thinking about time and space complexities.
How does a binary tree differ from a binary search tree?
A binary search tree fulfills an ordering search property. This means that there is a pattern that a binary search tree follows pertaining to how it stores its values. On any subtree, the left nodes are less than the root nodes, which is less than all of the right nodes.
What is a node?
A node represents a point in a tree.
What is the root of a binary tree?
The root is the topmost node in a binary tree. In the diagram above, the root of that binary tree is
What are leaf nodes?
A leaf node are external nodes, or nodes that do not have children. In the diagram, the leaf nodes are 7, 16, and 28.
What are internal nodes?
Internal nodes are known as the inner nodes that have at least one child. In the diagram, the internal nodes are 3, 6, 9, 14, 22, and 25.
A binary tree search is useful when you want to search through the tree to find a specific value. For example, say we want to search for 16 in the diagram above. We start at the root node of 10. The left child is going to be a smaller value than 10 and the right child will be larger value than 10. We know that 16 is larger than 10, so we will choose the right child, bringing us to 22. 16 is less than 22 so we choose the left node which brings us to 14. 16 is bigger than 14 so we choose the right node and leaf of 16.
What is traversing?
Traversing is a technical term we use to say how to we go through or walk through a binary tree.
What are the three methods of binary tree traversals?
Preorder: starting at the root, then left, then right
Inorder: starting at left, then root, then right
Postorder:starting at left, then right, then root
Conclusion:
This is just scratching the surface of binary trees! As I learn more I hope to elaborate more on the structure of binary trees and the methods involved.
Looking back, I realize that knowing these basics would have helped me along the way in understanding the past binary tree leetcode problems. It makes me wish that my bootcamp had implemented more time in the curriculum covering the basic datatypes. But I'm excited to uncover more about data types to help in my practice of building algorithms and to ultimately pass along my knowledge here!
This note extends to all of my posts, if there are any errors, questions, or better solutions to my posts, please feel free to reach out!
Resources:
https://www.youtube.com/watch?v=oSWTXtMglKE
Top comments (0)