Data Structures & Algorithms Notes Page

Definition:

• A binary tree is a set of nodes that:

  • Is either empty, or
  • Consists of a node called the root and two binary trees, called left and right subtrees, which are disjoint from each other and the root
  • The root of these subtrees are called the children of the root node

• There is an edge from a node to each of its children

• If $n_1, n_2, …, n_k$ is a sequence ofx nodes in the tree such that $n_i$ is a parent of $n_{i+1}$, then this sequence forms a path from $n_1$ to $n_k$.
• Path: A sequence of edges that goes from 1 node to another.
• The Length of a path is the number of edges in the path.
• If there is a path from X to Y, then X is an ancestor of Y, and Y is a descendent of X.
• The Depth of node X is the length of the path from the root to X.
• The Height of a tree is the depth/length of the deepest node.
• A leaf has no child.
• An internal node has at least 1 child.

Recursive Data Structure: