Binary tree is a widely-used tree data structure. Feature of a binary tree, which distinguish it from common tree, is that each node has at most two children. Widespread usage of binary tree is as a basic structure for binary search tree. Each binary tree has following groups of nodes:
- Root: the topmost node in a tree. It is a kind of "main node" in the tree, because all other nodes can be reached from root. Also, root has no parent. It is the node, at which operations on tree begin (commonly).
- Internal nodes: these nodes has a parent (root node is not an internal node) and at least one child.
- Leaf nodes: these nodes has a parent, but has no children.
Example of a binary tree
Basically, we can only define traversals for binary tree as possible operations: root-left-right (preorder), left-right-root (postorder) and left-root-right (inorder) traversals. We will speak about them in detail later.
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!