Binary Tree Terms
Binary Tree Terms
A tree has a root
and leaves
.
A root node
has no parent nodes.
A leaf node
has zero children.
A lef node
is an external node
, non leaf node are internal nodes
.
The degree
of a node is the number of children of that node.
The lines between nodes are called edges
.
Binary Tree Characteristics
- In a binary tree, each node has a maximum of two children.
- In a classic binary tree there is one root.
- There is only one unique path from any node to the root
An empty tree has no nodes, and should be considered a binary tree.
A Full Binary Tree
Every node that has a descendant has two descendants.
A Complete Binary Tree
When we fill out the tree we go from top to bottom and then left to right. All levels are completely filled out except the lowest level nodes which are filled from as left as possible.
A Perfect Binary Tree
All nodes with descendants have two descendants and all leaves are on the same level.
Height or Depth
A tree height is the number of edges
to reach the furthest node
.
The height
of a particular node
is the number of edges to reach the node
. The root
is at height
0.
Level
The level
of a node is the number of edge to traverse to reach the node
from the root
. The root
is at level 0.