| |
Binary Tree Vocabulary | page 3 of 7 |
A binary tree is a data structure where each node has two pointers, each pointing to another node or a NULL value.

The following binary tree terms will be defined and applied to the above example.
Root node - the top node in the tree; the node whose value is 52.
Parent node - a node which points to one or two nodes.
Child node - the node being pointed to from a parent; every node in the tree is a child to another node, except for the root node.
Leaf - a node that has no children
Level - the distance from the root, calculated by counting the shortest distance from the root to that node. Examples: 29 is the value stored in a node at level 1, 62 is a value stored in a node at level 2, 17 is the value of a node stored at level 3, etc.
Edge - an edge joins two nodes. In the above diagram each arrow represents an edge.
This tree is an example of an ordered binary tree that has the following property. For every parent node, a child to the right will have a larger value, while a child to the left will have a smaller value.
A subtree is the entire left branch or right branch of a node. For example, the left subtree of the node containing 52 has 4 nodes. The right subtree of node containing 75 has only 1 node.
A leaf will have two null pointers
|