[Data Structures] Binary Trees - 1

Binary Tree 

In a list, each node has up to one successor. In a binary tree, each node has up to two children, known as a left child and a right child. "Binary" means two, referring to the two children. Some more definitions related to a binary tree:

• Leaf: A tree node with no children.
• Internal node: A node with at least one child.
• Parent: A node with a child is said to be that child's parent. A node's ancestors include the node's parent, the parent's parent, etc., up to the tree's root.
• Root: The one tree node with no parent (the "top" node).

 

Depth, level, and height

A few additional terms:

• The link from a node to a child is called an edge.
• A node's depth is the number of edges on the path from the root to the node. The root node thus has depth 0.
• All nodes with the same depth form a tree level.
• A tree's height is the largest depth of any node. A tree with just one node has height 0.

 

Special types of binary trees

Certain binary tree structures can affect the speed of operations on the tree. The following describe special types of binary trees:

• A binary tree is full if every node contains 0 or 2 children.
• A binary tree is complete if all levels, except possibly the last level, contain all possible nodes and all nodes in the last level are as far left as possible.
• A binary tree is perfect, if all internal nodes have 2 children and all leaf nodes are at the same level.