Topics: Tree (Data Structure) - Data Structure
A binary tree is a tree in which every node can have 0, 1 or 2 children nodes. It’s used to save up memory and space, since other kind of trees can waste a lot of memory and space.
Formally, it’s defined as a homogeneous structure that’s the concatenation of a root node with two disjoint binary trees (called left sub-tree and right sub-tree).
Converting a Non-Binary Tree to a Binary Tree
To convert a tree that’s non-binary to one that’s binary, we can use the following process:
- Link horizontally the offspring of each node (i.e. link the siblings)
- Link vertically the parent node with the leftmost child, then delete the link between that parent and the rest of its offspring
- Rotate the corresponding diagram by 45°
The links to the left of a node represent parent-child relationships, while the links to the right represent sibling relationships.
Memory representation
A binary tree can be represented in memory as a register that contains three fields:
- The link to a children node (left link)
- Information in the node
- The link to a sibling node (right link)
| Left link | Info | Right link |
|---|