Binary tree

In computer science, a binary tree is a Tree Data structure in which each node has at most two children, which are referred to as the left child and the right child.

(“Binary Tree” 2022)

Types

• Complete binary tree
• Full binary tree
• Perfect binary tree
• Balanced binary tree
• Degenerate binary tree
• Skewed binary tree

Implementation

Representations

Array

Indexing

Assuming a 0-indexed array: child nodes for a node at index \(i\) are at \(\text{left}=2i+1\) and \(\text{right}=2i+2\). Similarly, the parent node for a node at index \(i\) is at \(\lfloor\frac{i-1}{2}\rfloor\).

Bibliography

Backlinks

• Balanced binary tree
• Binary heap
• Binary search tree
• Complete binary tree
• Degenerate binary tree
• Height-balanced binary tree
• Iterative deepening depth-first-search
• Perfect binary tree
• Succinct data structure
• Tree rotation