Trees terminology Flashcards
1
Q
Child
A
Self-explanatory
2
Q
Parent
A
Self-explanatory
Each node has exactly one parent, except root
3
Q
Root
A
The “highest”/”oldest” element in the tree
4
Q
Binary tree
A
A type of tree where each node can have at most two children
5
Q
Left/Right child
A
For binary trees, self-explanatory
6
Q
Ancestors
A
Nodes on the path to the root
parent, parent’s parent, etc.
7
Q
Decendants
A
Children, children’s children, etc.
8
Q
Subtree
A
A subset of a tree containing a node and its decendants
9
Q
Leaf
A
A node with no children
10
Q
Height (of a node)
A
The distance from a node to the deepest leaf of its subtree
11
Q
Depth (of a node)
A
Length of the path from the root to that node
12
Q
Balance factor
A
The height of the right subtree minus the height of the left subtree