For me, binary trees are the most difficult data structure to comprehend, possibly because they are not a linear data structure. I am still not the expert on this data structure but I want to share what I have learned for other beginners.
Binary trees have nodes that hold data and a reference to their children.
- The top node of a binary tree is referred to as the root node. It is the only node without a parent.
- In a binary tree, each node can only have 2 immediate children(one left child, one right child).
- A child is any node directly underneath a given node.
- Nodes on the same level of a tree that share the same parent node are referred to as siblings.
- A node that doesn't have children(bottom node) is referred to as a leaf.
One specific type of binary tree is a Binary Search Tree.
- In a binary search tree, the left child will always be less than the parent node and the right child will be greater than the parent node.
Iterating through the elements of a tree is called Tree Traversal. There are 2 main ways to traverse through a tree:
- Breadth-First Search - iterates through each level of a tree from left to right
- Depth-First Search - iterates through elements starting from the root, down to the root's left child, down the left child's left child, and so on until it reaches the left leaf. Then it backtraces to the parent and down to the right child and so on until it backtraces to the root. The process then starts again with the root's right child. For example, in the binary search tree above, using depth-first search would go traverse the tree in the following order: [ 20, 14, 9, 3, 11, 19, 57, 31, 62, 72 ]
If you have any suggestions for basic information to add, or any resources to help learn more about binary trees, please do not hesitate to comment!
Latest comments (0)