Rooted Tree

A tree where a vertex is designated as the root vertex.

Height

Length of the longest path from the root.

Level

For a given vertex $v$, length of the simple path from the root to $v$.

Parent

For a given vertex $v$, its parent vertex is the unique vertex $u$ where $\text{level}(u) \lt \text{level}(v)$ and there is an edge between $u$ and $v$.

Child

For a given vertex $v$, $u$ is a child of $v$ iff $v$ is the parent of $u$.

Siblings

Vertices with the same parent.

Ancestors

For a given vertex $v$, all vertices in the path from the root to $v$, excluding $v$ and including the root.

Descendants

For a given vertex $v$, all vertices that have $v$ as their ancestor.

Leaf

In a rooted tree, a leaf does not have any children.

Internal vertices

Vertices that have children.

Sub-rooted tree

Suppose $a$ is a vertex in a tree. Then the sub-tree with $a$ as its root is the sub-graph of the tree consisting of $a$ and its descendants and all edges incident to these descendants.

Decision tree

Vertices represent the decision points or events, where a decision could be made. Edges represent the possible decisions/outcomes of different choices.

Representation of Algebraic Expressions

There are 3 common forms of algebraic expressions.

Infix form

The symbol is written in-between the operands. The form we usually use.

Example: $x*y$

Prefix form

Aka. Polish form. The symbol is written before the operands.

$x*y$’s prefix form is: $* x y$

Parantheses are not required.

Postfix form

Aka. reverse Polish form. The symbol is written after the operands. Used commonly when parsing algebraic expressions in calculators.

$x*y$’s prefix form is: $x y *$